Mario is an international powerhouse. No question. Super Mario Brothers was packaged with every NES sold, so that automatically put it on top, in terms of sales.
The highest selling game that was *not* packaged with a system is the first set of Pokemon games. That even outsold Tetris, which was a pack-in with the original Gameboy.

http://everythingandnothing.org.uk/vg/worldtotals.php

As for the *best* game of all time, that could lead to an endless debate. To be safe, I'll pick the first and 3rd Super Mario Bros for now. Sure, there are better games that came after them, but every game afterwards still looks back at 'em as a guideline. That's power.