Cheapest Terraforming Mars

A youtube video suggests a really, really, cheap way to terraform Mars.

Bacteria. Little bacteria genetically engineered to endure the high radiation, low temperature nightmare that Mars is now, slowly pushing it warmer, wetter, gassier, and more able to help us.
The cost? He estimates it to be about "two shuttle launches," which would add up to $120 million USD at lowest and $2.6 billion USD at highest. Both are astronomical sums, but well within the reach of multiple nations, and even a few corporations.
The bacteria would work slowly, but would operate in conjunction with any other project undertaken. Warming Mars with lasers would speed it up. Adding CO2 would speed it up. Dropping resource-rich meteors would speed it up. A coal-burning remote base would speed it up.
He points out that a common objection to this kind of thing is "but we have problems here on Earth!" Which we do. For $2.6 billion, apartment complexes could be built in such numbers that rent prices would collapse nationwide, ending homelessness for the foreseeable future. Or, a comprehensive medical anti-drug program could end narcotic addiction. Or any number of other worthy projects.
However, another big benefit to this project is that it can be piggybacked on a scientific mission, the kind we were planning to do anyway, for only marginally more money. An extra $500 on a billion dollar project. And that makes it a little harder to argue.