There's also the Final Fantasy IX song Grand Cross. While not being sung by Necron himself and not having lyrics at all, this is still a music that contains lot of people screaming in panic and agony, which kinda goes along with Necron, being the embodiment of humans' fear, helplessness, and suffering when faced with death.
Jonathan Coulton's "Still Alive", the famous ending theme from Portal; unusually enough, it's sung by GLaDOS after she's defeated by Chell, but it still keeps the basic Villain Song structure. It's also unusual in having a cheerful, upbeat tune and having lyrics which are very passive-aggressive for coming from a villain.
The second game features a similar ending song: Want You Gone. Rarely for a sequel villainous song, it approximately equals the original in quality (often actually creepier).
Then again, GLaDOS was no longer even the villain during the last portion of the game anyway and even helps you out to an extent. It's more of an Anti-Villain Song at that point.
Arguably, again from Jonathan Coulton and again in a VALVE game — one of the songs that plays on the jukeboxes scattered around Left 4 Dead 2 is "Re: Your Brains", a song about an office worker turned zombie telling his still-human surviving coworker what he and his flesh-eating companions will do when they get to him. Bonus: When the chorus starts up, an in-game Horde attacks. And they snarl in-tune to it.
Conkers Bad Fur Day has "Sloprano", an opera sung by the Great Mighty Poo, a giant singing pile of feces. The song is actually key to defeating him, as he sings higher and higher notes as you attack him, until finally he sings a note pitched high enough to shatter the glass blocking the toilet cord.
Marjoly and crew also have such songs in the game's two sequels, and in the 2nd game the villain Akujo has a similar tune.
"Kuttetekaruna", from Loco Roco, has no "real" lyrics to speak of... but it's hard to call it anything other than a villain song, given the frightened voices of its singers and its use of maniac laughter.
It gets even better in the sequel, where Mojyas get their own theme which they use to muck Locorocos' world. Man, they may be evil, but they sure sing a catchy song (even if its lyrics are complete gibberish)! And did I mention that three out of four bosses have their own version of it?
The War Song from Abe Lincoln Must Die! may just qualify, as while the character isn't particularly villainous, his desires certainly are, as revealed by his love of bombs and guns (And so much more!) and his unbridled joy that a war has begun.
Sam & Max Beyond Time And Space: T-H-E-M gets a big mariachi musical number in Chariots of the Dogs explaining why they steal souls in a time-traveling flying saucer.
While not a traditional Villain Song, Hazama's (a.k.a. Terumi Yuuki's) leitmotif, "Gluttony Fang", from BlazBlue is so awesome it deserves a mention. The same holds true for his final boss theme, "Endless Despair", that perfectly captures the spirit of someone about to give you the Curb-Stomp Battle of your life. If BlazBlue was a musical, this would definitely be Hazama's big ol' showstopper.
There's now also a vocal version of both themes and yes, the lyrics, that seem to have been marinated in Hazama's evil over the weekend, do answer all criteria of a full-blown Villain Song.
Again, while not quite a Villain Song as it has no lyrics and is not performed by the villain themself, Relius' theme Plastic Night is concentrated evil in music form.
With the release of Chronophantasma and its remixed soundtrack, all of the above songs were reworked. Gluttony Fang II became more hectic and classy, Plastic Night II gained a badass piano and giant ominous intro and outro, and Endless Despair II sounds much more evil and oppressive. There's also the newcomer Azrael, who brings two songs: The Tyrant, which is about close as music can get to screaming at you to run for your life, and GO in SOUL, the hammy as hell vocal version performed by his seiyu.
The educational computer game I. M. Meen opens with a catchy Villain Song from the titular villain about his plan to trap studious little bookworms in a magic labyrinth using a magic book. It almost makes up for the fact that it and all other cutscenes were animated by the same people who animated the dreaded The Legend of Zelda CDi Games.
For Sonic Adventure 2, the theme for Biolizard boss battle, Supporting Me:
"I believe in my future, farewell to the shadow. It was my place to live, but I need your hand. Lead me out with your light, I've breathed in the disgusting air of darkness, but I never lose out."
Though not exactly evil, Team Dark's (Shadow, Rouge, and E-123-Omega) theme This Machine is arguably the best theme among the 4 teams' theme songs, and it's about the three members of the team who were marked as villains in the previous game, or built by the villain in Omega's case.
They also brought back Throw It All Away and All Hail Shadow. Also, Shadow's page on the Sonic wiki has a whole section of theme songs related to him, and it even makes of note of saying that the lyrics are hard to understand in most of them. Oh, and for a mind boggler, remember Live and Learn? Yeah, the main theme and final boss music of Sonic Adventure 2? They actually attribute that as his theme.
Which actually makes sense, considering that the song is about letting go of the pain in one's past.
Metal Sonic has many themes (Yes really!), which fit him extremely well:
From the Genesis era, "Metal Sonic" from the Sega Virtual Tunes, about his purpose and personality.
From Mystical Ninja Starring Goemon, we have Spring Breeze Dancin' and Kitty Lily's secret weapon: Gorgeus My Stage. An awesome Broadway-styled musical act that, without a doubt, will turn anyone into a Peach Montain Shogun "hard-die fan". Or so they claim.
"Look Pimpin'" from MadWorld is a hip-hop Villain Song by Sick YG, sung from the perspective of the Final Boss, the Black Baron, during the game's climactic battle. Once half the boss's health is gone, the music switches to "So Cold" by Ox, which is still a villain song; however, while "Look Pimpin'" mocks Jack for thinking he can defeat the Black Baron, "So Cold" is him enraged by how he's gotten beaten up.
The other boss themes are also villain songs, though not as focused. "You Don't Know Me" by Bandy Leggz (the female boss music) in particular is girl power gone mad.
"Nightfall" from Warcraft's own rock band Level 80 Elite Tauren Chieftain starts out as a villain song sung by a death knight of the Ebon Blade, before the end describes the Knights being betrayed and swearing vengeance upon the Lich King.
"Ignorance Is Bliss", by Jellyfish, is sung by Bowser to Peach. It came out on the album "White Knuckle Scorin'", which had a comic story insert based on Super Mario World. (Although the comic had the characters continually referencing the titles of the songs on the album, this song was the only Mario-themed song on the album.)
Don't forget Aribeth's theme (from Neverwinter Nights) when she does a complete face-heel turn. Their "evil theme" is played when the Player character encounters them near the end of the game and can also be found in the game's toolset.
Ape Escape 3 has "Banana Heartbreak"; it's not so much a Villain Song as a song by a villain for most of it, but in the last verse it turns twisted by Ape Escape standards.
Agreed. Nothing says "theatre" like multiple-personality barbie-esque monkeys in pink dresses. Just sit back and listen to banana heartbreak/I WILL CRUSH YOU.
When a song from the Shin Megami Tensei series is used, it's usually in the Persona series and about how awesome the heroes are or cheering them on to their goal, maybe something a bit deeper. Shin Megami Tensei III: Nocturne seems to be an exception. The Fierce Battle theme seems to be the angels singing to you in hatred for how you've abused your power to go against them while the main Boss Battle theme is the demons singing about why God despises them, with a bit of the desperate remains of humanity (and possibly a few demons) begging for salvation. Each of these sides can be villains to you in the end.
Mr. Scratch, the Big Bad of the Alan Wake DLC American Nightmare, gets his own theme demonstrating his psychopathy, called "The Happy Song". It also plays during the big confrontation with his Elite Mooks at the end of the game.
An interesting example is "That's Amore" of Psychopath Bibi Love from Dead Rising 2. At first listen, it really doesn't sound much more than what you'd expect of a love song. But consider it has lyrics like "You better do what I say!/Say you love me today!" when she's threatened to blow up several innocents unless you help her performance.
Anarchy Reigns has a few of these around. Baron's new track doesn't fit since he's fighting with the good guys here, but there are two better examples. First there's Max's theme Unlimited Resources, which is basically Max singing to you about how he is just going to wreck your shit. The other song is the final boss track against Nikolai called Find You. The song takes place from the villain's perspective completely and how his view of the world has become dark and hopeless, telling Jack and Leo that their only option is to find the truth before the truth find them.
In Nazi Zombies, "Not Ready to Die" definitely seems to be Dr. Richtofen's villain song, while "115" seems to be Samantha's.
Scooby-Doo! Night of 100 Frights features four Villain Songs for each of the four bosses: the Black Knight, the Green Ghost, the Ghost of Redbeard, and the Big Bad, Mastermind. For the first three, it's just a background choir during the fight, but Mastermind has a few lines in his song.