We had a similar situation at that age, so I believe it's nothing unusual, even though seeing your child in fear can be quite upsetting.
The only solution we found is to give in for a few weeks, until the anxiety settles down: Sit with him until he sleeps, and if he wakes up in the night you need to do the same. It is important to address this issue: talk to him about it, and explain that there is no reason to be afraid, and that you will always be there for him.
After a week or two, he will know that you are always there, and feel reassured. At that point you can start the next phase: Slowly easing out of staying with him. Here you will need to experiment, to see what is acceptable to him, and what isn't, for example:
Stay a limited amount of time, say 5 minutes. Tell him beforehand that you will stay with him for five minutes, and announce when the time is up
Leave the door open. This was the key point or us: When we offered to leave the door to our daughter's room open, she accepted that we left the room before she was asleep
One final tip: Beware of creaking floor boards - I had to learn where not to step, in order to avoid making noise that would have her standing in her bed screaming within a 10th of a second...
Edit:
One item I forgot:
- Leaving the light on when we put her to bed. The main light in her room has a dimmer. We turn it to the lowest setting, which leaves a very faint glow. She is 3 1/2 now, and still insists on this.