Here's a problem: I looked at the no-warps run, and it has a final score of 662800. You need to score more than 10000 extra points per level. You need to (for example) get 2 fire flowers, grab 30 more coins and smash 51 extra bricks to get that much in an average level. Of course, some levels might have higher reachable scores.
I found a nice little guide at
http://www.neoseeker.com/resourcelink.html?rlid=62237&rid=57598
Adding up the total scores the player got for each level, I found that they do add up to more than 1 million. However, subtracting the points for time at the end of castle levels, and for red coins and yoshi eggs (this is the deluxe gameboy edition, not the NES) it is less than 1 million. However, it shouldn't take much (brick busting, anyone?) to clear that mark. Or, preferably, hit 999,950. I think that 999,950 would look best. Some arbitrary 1,000,000+ number would not seem as impressive as 999,950 or even 1,000,000. This is because achieving that precise figure looks like luck, but then they realise how hard it must have been to do it. I think 999,950 is more impressive than 1,000,000 because if the viewer was anything short of an expert at Mario, he would think that anything more, i.e. 1,000,000, would roll the score back to 0. 1,000,000 or 1,057,250 (random number) imply that a higher score could be reached.