There's also Avada Kedavra as sung by Voldemort, Wormtail and Draco Malfoy. It was made by "Albino Blacksheep" and "Too Much Spare Time Animation" and parodies The Lion King's Hakuna Matata.
The song was actually made by a band named Nuclear Bubble Wrap, sung by the two main singers Jace McLain and Kyle Thorne, with guest singer Steve Goodie as Voldemort. And by God was that the right choice.
It helps a bit that the latter part of Everything You Ever, between the second and third verses, has sort of a Dark Reprise, with a chorus in the background singing to the tune of Brand New Day.
Though because Dr. Horrible is a Villain Protagonist, (and at least three of his songs describe his villainous motives), this trope is probably better exemplified by Captain Hammer's Everyone's a Hero in Their Own Way near the end of the film, which demonstrates he's a complete jerk while superficially sounding heroic.
Everyone's a hero in their own way Everyone has villains they must face They're not as cool as mine But folks, you know it's fine To know your place...
Given how unnecessarily brutal he is to Doctor Horrible (he could probably have stopped him without grabbing him by the neck and slamming his head into a van or throwing a car at his head) and the fact that he tries to murder Dr. Horrible in the end (granted, Horrible intended to murder him first, but two wrongs don't make a right), one could perhaps argue that Hammer is also a villain anyway. That would make Everyone's A Hero a straighter example of this trope and A Man's Gotta Do an unusual case of a villain song started by one villain and then hijacked by an opposing villain (since Horrible starts it and Hammer takes over).
And the two versions of the Bad Horse Chorus, sung on behalf of the Evil League of Evil's leader.
It can be argued that every song in Dr. Horrible's Singalong Blog is a Villain Song except for 'Caring Hands' and 'Penny's Song' (both of them being sung by Penny). 'My Freeze Ray' is somewhat on the ropes, it's more about love, but it has it's more sinister lines, plus it's sung by the anti-villain anyways. So They Say is similar in that the majority of it isn't evil, though Captain Hammer and Dr. Horrible both have lines in the song.
Played with in New Kids On The Rock's Ryan's Christmas Wish: The Large Ham villain The Misery Meister gets his own jaunty alliteration-filled villain song (which occurs about 11:51 into this video), but the flashiness is limited to intentionally stiff dancing, tossing rag dolls around, and menacingly wielding a small meat grinder, and after a verse we flash forward two minutes later to the very ending of the song.
In "Get Back To Hogwarts", Draco's verse is about how he's going to replace Harry as the most popular kid in school. Not exactly villainous, but still antagonistic.
Someone created a Filk Song of Magneto and Xavier singing Defying Gravity from Wicked, in which Magneto abandons Xavier's plans for peaceful coexistence with humans. It's somewhere between this trope and an "I Want" Song. Quite awesome.
Edward's song in Twilight The Musical with the notable line "I'll show you anaphase when I rip you in two." Way better than the actual Edward!
Film Cow's "Make Me Smile", sung by a psychotic anthropomorphic ferret definitely counts. It's a cheerful, jaunty tune that features holocaust denial, a pro eugenics attitude, molestation, murder and cannibalism. It's absolutely hilarious.
An unrelated musical adaptation of the same name on reverbnation.com gives three songs for Dr. Heiter: "The Pieces are in Place" when he has all three of his test subjects together, "Putting it Together" when he constructs his human centipede, and "Dieter Sings Some Shit About a Gun Fight" when he is confronted by the police and ponders what to do.
By the same people as MEDIC! is Senpai Notice Me, sung by Yandere-chan about how she'll kill, maim, and frame people for murder if it means she gets Senpai to herself. The idea of Villain Songs is lampshaded in the stinger.
Midori: YandereDev! YandereDev! Isn't it a bad idea to sing loudly about murdering people?
YandereDev: Silly Midori, musicals don't use normal logic. You can sing about anything!
Ultra Fast Pony has "Discord Games", where instead of pointing out their shortcomings in regular conversation, Discord decides to break them in song.
In PONY.MOV, Fluttershy constantly tells the other characters to stay out of her shed. When some of the characters don't heed this, she revs up a chainsaw and prepares to punish them by singing "Gonna Eatcha Brains". For the record, it's sung to the tune of the Fat Albert theme song.
The end of Episode 51 of Dragon Ball Z Abridged has the newly-achieved Perfect Cell singing "P.E.R.F.E.C.T.", a parody of beauty pageant victory songs, combining Team Four Star's usual brand of humor with the Oh Crap! of the other characters and the viewers now that Cell has achieved his ultimate goal.
The end credits of RWBY Volume Three has "Divide", an absolutely terrifying song from the point of view of Salem, talking about her plans and how she will absolutely crush anyone that Ozpin sends her way.
Earlier in the volume, Mercury and Emerald got one called "I'm the One", heavily mocking those who they are going up against, especially given that their opponents think they're just 'students', and not the son of an assassin he killed himself, and a thief who uses illusions to manipulate people into doing what she wants.
A lesser example would be "Neon", the theme of Neon Katt, which is less evil, and more ego, with her playfully informing her opponents that there is no way they can be as cool as her.
Ratboy Genius: Little King John sings two in RBG Dreams Minecraft:
After kidnapping Summer, he sings the creepy Potato Knishes song, although it's more about the things he makes in his factory than about how evil he is.
However, he later got another one in the first Interlude, largely about stealing Happyman's factory for himself.