I saw some of those videos on Youtube also. Its pretty damn good talent to use Mario Paint's music composer to create various tracks from games considering how limited the feature is.

Its too bad Nintendo didn't come out with a new version of Mario Paint though it was supposed to be out for the Nintendo 64 (64DD) in the past but bit the dust.