Your dog is most likely exhibiting separation anxiety. Here are some things you can so to help:
Desensitize him to your departure cues. This means practice picking up keys, putting on coat, whatever you normally do when leaving the house, and then just sit on the couch and hang out. You want him to get to the point of no longer having much response to the departure cues.
Short absences are very helpful. Leave the house as normal but just drive around the block and return without fanfare. Departures and arrivals should be low-key. We don't want to associate heightened emotion with your coming and going. The ideal way to get a dog over separation distress is to start with these very short absences and gradually increase time away. Long absences do impede progress but mixing them with very short ones helps. This dog has been abandoned at least once already. He has that experience in his his history so he is predicting he will be abandoned again. When you leave and just drive around the block and return, it helps convince the dog that when you leave, you likely will come right back so no need to worry.
Give him something to focus on when you leave the house. Try a BusterCube, a puzzle game, or a kong stuffed with peanut butter (put in the freezer overnight so it will last longer).
See if the Thundershirt helps. There is a money back guarantee so definitely worth a try.
Leave on classical music or a cd specially designed to calm dogs:
Through a Dog's Ear
DAP plugins
Play the magnet game to reinforce the idea that calm behavior brings you back to him and anxious behavior keeps you away. Once he catches on to that concept, raise criteria and require longer and longer periods of calm in order for him to earn his reward of you returning. Here is a general idea of how to play the magnet game:
1) Dog is tethered, owner stands at a distance.
2) Calm behavior draws you to him like a magnet.
3) Hyper or anxious behavior repels you.
4) When your dog remains calm long enough for you to make it all the way to him he gets a soothing massage.
5) Reset and repeat.
No commands are given. The dog learns that his choice to behave calmly is what earns him the reward.
Avoiding eye contact may help your dog remain calm. Try this if your dog is having trouble catching on to the game. Act very casual and observe him from your peripheral vision.
Initially, reward the slightest try in the right direction. If your dog goes from straining on the tether to not straining as much, reward that with a step toward her. As he catches on to the game, gradually raise your criteria as to what qualifies as appropriate calm behavior.
You can use a variation of the magnet game if the dog is particularly bonded to one person. That person can go outside the house while a helper observes the dog inside. As soon as calm behavior is exhibited the helper alerts the owner to return. I use walkie talkies for this exercise. Gradually increase the length of time calm behavior is required in order to bring the owner back.
Film when you're away to monitor progress.
Here is some more information about separation anxiety:
Separation Anxiety | ASPCA