This blog post has a detailed analysis of the deaths from various forms of energy. It would seem to agree with the result of a large number of deaths saved from the use of nuclear energy.
For just air pollution it says:
The World Health Organization and other sources attribute about 1 million deaths/year to coal air pollution. Coal generates about 6200 TWh out of the world total of 15500 TWh of electricity. This would be 161 deaths per TWh.
So 1 million deaths per year from coal air pollution. Nuclear power provides ~6% of the worlds energy, and so over 20 years over a million lives will be saved. This seems to make the claim in the original paper seem feasible.
Other forms of energy are also compared for total deaths per TwH:
Energy Source Death Rate (deaths per TWh) CORRECTED
Coal (elect, heat,cook –world avg) 100 (26% of world energy, 50% of electricity)
Coal electricity – world avg 60 (26% of world energy, 50% of electricity)
Coal (elect,heat,cook)– China 170
Coal electricity- China 90
Coal – USA 15
Oil 36 (36% of world energy)
Natural Gas 4 (21% of world energy)
Solar (rooftop) 0.44 (0.2% of world energy for all solar)
Wind 0.15 (1.6% of world energy)
Hydro 0.10 (europe death rate, 2.2% of world energy)
Hydro - world including Banqiao) 1.4 (about 2500 TWh/yr and 171,000 Banqiao dead)
Nuclear 0.04 (5.9% of world energy)
This is also shown visually: