As in the case with nearly every time you have a problem player...talk to him outside of the game.
He may be used to playing games with people that are okay with that kind of behavior (I've run into a few very backstabby parties in my time), and might be completely okay with the in-game ramifications of what he does. It might just be what he expects to be happening. So, it might not be a 'warning' in-game to him...it might just be the game working the way he expects it to.
That's the problem with in-game hints...people can miss what you are trying to say. Or they can interpret it as you being mean to them and punishing them for playing their character the way they want to.
So you need to make it clear that there's a problem. Tell him what you've told us, tell him what other players are saying, and ask if he is willing to tone it down a bit. He might honestly have no idea that the other players are so aggravated at him.
So, ultimately, you need to sit down and talk to him, privately, away from the rest of the group. Calmly explain what is going on, and see what he has to say.
He might apologize and shape up. He might laugh you off and ignore you. He might scream in your face...be ready for any of these possibilities.
But...if he doesn't shape up after you've talked to him and expressed that his behavior is not okay, it's time to put your foot down as the DM. If the polite approach doesn't work, then tell him something like this:
"I'm sorry to say this, then. But, as the DM, I need to make sure that the rest of the party is having fun, too. And they aren't. Because of you. If you are not willing to play with us in a way that we can all enjoy...I'm afraid I'm going to have to ask you to leave the game."
Give him a chance again, here, to promise to shape up.
But, that's your final option. As DM, you have the authority to expel a player from your game who is causing problems. It is better to expel a single player than to see the rest of the group abandon ship, leaving you stuck with the problem player.
So, short version:
Talk to him in private, explain to him that his behavior is making other players want to quit. Ask him if he's willing to change. If he refuses...it's time to ask him to leave the group. Be polite the entire time.