An article by Huff et al. in the NY Times summarizes research published in the PNAS that examines human genetic history for information about early population size.
The authors' point estimate of the size of the human population 1.3 million years ago is 18,500, with a 95% confidence interval that stretches between 14,500 and 26,000. In fact, this roughly corresponds to the estimate of Harpending et al., published in 1998, of around 10,000. What's remarkable is the comparison in the Huff article of the relative sizes of various primate populations. According to this evidence, early humans were by no means more plentiful, i.e., evolutionarily successful.