I'm not sure if this is considered covering: The Megas take Megaman songs, play them, and add lyrics over them. They're technically covering the song but also adding lyrics. I'm guessin' that works too, so here ya go:

http://www.youtube.com/watch?v=UUYSriP4lmM - That's one of their more famous ones, Airman's stage.

They've done one non-Megaman over, but that was of "Sunglasses at Night", which isn't video game related. They've done a Megaman 1 album and a Megaman 2 album, they're working working on 3.