This was a remake (kinda) of Wily Castle 1-2 from Megaman II. Despite the man's badly cracking voice, it's an awesome song (and it's been stuck in my head for about six hours)
YouTube - Okkusenman (English Subtitles)
What I don't get is how Japanese songs have very depressing lyrics but they sing them in a very upbeat tune.