The article itself cites the Guardian, who cites the European Environmental Agency, who cites REVIHAAP, which is only a review. REVIHAAP (http://www.euro.who.int/__data/assets/pdf_file/0004/193108/R...) mentions a lot of studies that estimate the proportionality factor between mortality and NOx concentration. This is precisely the method I described above: assume proportionality, then estimate the proportionality constant, then multiply by millions of people and get a scary number. Few studies in the REVIHAAP report cite actual concentrations, but when they do they are invariably much higher than the 20µg the EEA applies as lower cutoff.

(The study you linked to doesn't include NOx. REVIHAAP itself has more inapplicable stuff, such as one study that actually looked at proximity to roads, then noted that they can't tease apart the effects of NOx, ozone, soot, etc, then proceeded to make a claim about NOx specifically anyway.)