Cumulative percentage of population by Nth surname ~ N^(3/5)for a fairly wide range of large countries. (3/5 is only true for the US and England; otherwise it sort of varies between 3/5 and 2/3: the US is at .588, England at 0.606, Germany at 0.61, Australia at 0.63, Russia at 0.637, and Japan at 0.65.) In all cases the power-law dependence is quite good. (I really ought to put up the graphs but I'm too lazy to.) For smaller countries the picture is somewhat mixed, the exponent tends to be somewhat higher on average (Scots at 0.76, N. Irish at 0.88) but in some cases -- Hungary and Sweden -- the dependence clearly isn't power-law.
Poking around in the literature I found nothing much except this old paper that describes finding something similar but doesn't have a theory (JSTOR required):
The Distribution of Surname FrequenciesI imagine this is one of those Zipf's law effects but I'm unclear about what kinds of processes would give rise to a Zipf's law in this context. It's esp. interesting to me that Japan fits so well in this series given cultural differences etc. Would also like to know if the exponent is really size-dependent.
Wendy Fox and Gabriel Lasker
International Statistical Review 51, 81-87 (1983)
Oh and to answer the original question I estimate that it'd take about 650 names to cover 50% of the US, and about 400 for the UK. I think these are underestimates.
UPDATE the graphs are up here.