I think anger is a good bet for the OP if he really wants an evil-evil character. If the player character is given reasons to become extremely angry, it will make his choices seem less deranged. The better reasons for him to be angry, the more likely the player will be following right along with him.

Lex Luthor is a good example. Or at least in Smallville. There are tons of followers of his character. Even fanatics who hate Clark's character because of it. The guy has it rough. And to make matters worse, his rival is Superman. He's only human, he's been dumped on his entire life, and he still rises to meet an impossible challenge, with ego intact.

I like villains that think they are really saving the world. Real life is not presented in black and white, it's in shades of gray. This means that the hero can have a similar goal to the villain -- to bring a better future. But the villain's idea on how to bring a better future may be complete opposite to the hero's.

IMO, the player needs to think they are the main character, whether it be hero or villain. If the villain goes around burning villages of innocent people, it could make the player stop caring for the main character and see that it is just a game. The only exception (that I can think of) is if the player is given the choice whether to do something bad, such as in games like Fable. This helps keep the realism alive in the game.

Anyway, that's my 2 cents.