How many reference letters requests is considered too many? The problem with me is that I applied to 4 programs and I didn't get in in any of them. The last program which was almost guaranteed admission (because I already found a researcher willing to accept me); I emailed my undergrad thesis supervisor for, what I called at the time of the email "my last reference letter request ever to make". Unfortunately, I wasn't accepted to the program and now I'm applying again to a different school.
The problem is I feel so weird about emailing him again for another reference letter. Other than the generic email, how can I go about emailing him? I am sure he remembers me , but I don't know how to justify the amount of requests that I've sent him so far !

Any idea on how I should approach the issue?
You haven't asked for too many.  Write to your supervisor, tell him what happened, and ask whether he will write "a few" more reference letters.  People will generally be willing to help you if they understand the reasons for your requests.  (Do not ask for "one more" or you could find yourself in the same situation again.)