I'm pretty sure it's Rock as in "rock 'n' roll". His sister is named Roll, and I believe the opening of Mega Man 4/IV reconfirms that Mega Man's name is Rock.
Sure, he doesn't seem like a rock star. But for some reason this series has musically-themed character names. If Roll was more involved in the games, "Rock & Roll" would make more sense, but whatever. Then Proto Man is named "Blues" in Japan. Ironic since he's not the blue one, but it likely refers to the type of music. Don't forget Bass (Forte), Treble (Gospel), Beat, and the little-known Tango. (I think in the Xtreme games there's also a character named Midi...)
Not sure how Rush, Fliptop (Eddie), Otto, Duo or King fit in, though...
As to why he's "Mega" Man and not Rock Man outside of Japan, probably people would think of the other kind of rock. Maybe in Japanese, "rock" (as in stone) and "rock" (as in rock 'n' roll) aren't the same word? "Mega" sounds cool, and alliteration is apparently catchy.