The Atlantic actually did an article about this very question (and various other, related topics) back in 2002, titled 1491. It notes some very interesting points, including that we do have actual records of death rates, from Spanish missionaries who settled in the area:
[Henry F.] Dobyns began his exploration of pre-Columbian Indian demography in the early 1950s, when he was a graduate student. At the invitation of a friend, he spent a few months in northern Mexico, which is full of Spanish-era missions. There he poked through the crumbling leather-bound ledgers in which Jesuits recorded local births and deaths. Right away he noticed how many more deaths there were. The Spaniards arrived, and then Indians died—in huge numbers, at incredible rates.
Smallpox was only the first epidemic. Typhus... influenza and smallpox together... smallpox again... diphtheria... measles... all ravaged the remains of Incan culture. Dobyns was the first social scientist to piece together this awful picture, and he naturally rushed his findings into print. Hardly anyone paid attention. But Dobyns was already working on a second, related question: If all those people died, how many had been living there to begin with? Before Columbus, Dobyns calculated, the Western Hemisphere held ninety to 112 million people. Another way of saying this is that in 1491 more people lived in the Americas than in Europe.
Indeed, the calamity wrought by [Hernando de Soto's expedition] apparently extended across the whole Southeast. The Coosa city-states, in western Georgia, and the Caddoan-speaking civilization, centered on the Texas-Arkansas border, disintegrated soon after Soto appeared. The Caddo had had a taste for monumental architecture: public plazas, ceremonial platforms, mausoleums. After Soto's army left, notes Timothy K. Perttula, an archaeological consultant in Austin, Texas, the Caddo stopped building community centers and began digging community cemeteries. Between Soto's and La Salle's visits, Perttula believes, the Caddoan population fell from about 200,000 to about 8,500—a drop of nearly 96 percent. In the eighteenth century the tally shrank further, to 1,400. An equivalent loss today in the population of New York City would reduce it to 56,000—not enough to fill Yankee Stadium. "That's one reason whites think of Indians as nomadic hunters," says Russell Thornton, an anthropologist at the University of California at Los Angeles. "Everything else—all the heavily populated urbanized societies—was wiped out."
It also points out that not everyone agrees with this view:
"Most of the arguments for the very large numbers have been theoretical," Ubelaker says in defense of low counters. "When you try to marry the theoretical arguments to the data that are available on individual groups in different regions, it's hard to find support for those numbers." Archaeologists, he says, keep searching for the settlements in which those millions of people supposedly lived, with little success. "As more and more excavation is done, one would expect to see more evidence for dense populations than has thus far emerged." Dean Snow, the Pennsylvania State anthropologist, examined Colonial-era Mohawk Iroquois sites and found "no support for the notion that ubiquitous pandemics swept the region." In his view, asserting that the continent was filled with people who left no trace is like looking at an empty bank account and claiming that it must once have held millions of dollars.
The low counters are also troubled by the Dobynsian procedure for recovering original population numbers: applying an assumed death rate, usually 95 percent, to the observed population nadir. Ubelaker believes that the lowest point for Indians in North America was around 1900, when their numbers fell to about half a million. Assuming a 95 percent death rate, the pre-contact population would have been 10 million. Go up one percent, to a 96 percent death rate, and the figure jumps to 12.5 million—arithmetically creating more than two million people from a tiny increase in mortality rates. At 98 percent the number bounds to 25 million. Minute changes in baseline assumptions produce wildly different results.
Nevertheless, it brings up several points that are difficult to ignore in support of the theory that there were a lot of people living in the Americas, such as multiple accounts of population explosions of species whose numbers used to be kept in check by human activity.
It also points out, unlike Joe's characterization of maize as a substandard, borderline foodstuff, that the plant was so ridiculously adaptable that when it made it back to the Old World it set off population booms everywhere from England to Eastern Europe to Africa. (One of the more tragic side effects outside the American continents was, in fact, the maize-fed African population boom, which led to increased tribal warfare in Africa, which led to them having plenty of prisoners to sell to European slave traders. Every American knows how that eventually turned out, in our part of the world at least...)