Megaman uses two palette sets: 1st for his whole body, 2nd for his face.
But he's referring to the select screen, which I presume is using background tiles. I don't know what that screen does with palettes that makes it unusual, as I haven't had a look. It's not unknown to use a few well-placed sprites to boost the colour possibilities of a static screen, however.
Given how much Mega Man hacking you've done, Zynk, I guess you know how that screen works.
EDIT: Aha, now I've had a look at the game, I can see what's happening, and it's what I expected. Everything is BG tiles except for everyone's skin, Mega Man's eyes, and bits of Spark Man's head, which are all sprites. That's how they get around the colour limitation, like I guessed. So if you want to edit that title screen, you'll need to use a combination of BG tiles and sprites.