Wow, three feet of cross stitching makes me wince, unless it's like 2ct.
The Spriter's Resource has a fantastic collection of sprites (the original graphics in all their pixelated glory). For MM2, the boss page is here:
http://spriters-resource.com/nes/mm2/sheet/2321
For the one I'm working on right now, I actually created the whole thing from the sprites on that site. 8-bit doesn't translate to being too big, and each of those bosses' original pictures are only 30x30 pixels. That means on 11ct, you've got about three inches per boss.
Using this would be great for all nine on one pillow. Not so good if you want the yard by yard measurements

. But I do believe that KG Chart (as well as PCStitch and XStitch, though I only have the trial versions of those programs) can do it without the weird stuff that happens with Photoshop and its ilk. (If you do create your own picture, be sure to save it in .bmp or .png form. These will not anti-alias the coloring, although Photoshop 5 really mucked up some colors a couple times. Dunno what that's about).
In addition, go with the picture that's the closest to the original. Often times (especially with jpegs) anti-aliasing takes place, adding WAY more colors than are really necessary. Remember, Mega Man was 8-bit... the shading wasn't really too great, even by his second game. I'm currently using five colors for him; skin, eye-whites, black, and two shades of blue, despite the programs and pictures I originally tried to use making him have about 5 shades of blue, and two skin tones.

So be aware that whichever picture you choose, the stitching program will probably insert a lot of extra colors when you're using a file that isn't straight-up from the game.
Hope that sorta makes sense and offers some helpful advice...