For what it's worth, the FAQ on his blog dances around this topic:

"Running Shor’s algorithm to break the RSA cryptosystem would require several thousand logical qubits. With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today."

In terms of limited connectivity: mesh connectivity is theoretically sufficient. Putting all qubits in superposition in a preparation phase then allows you to do any arbitrary quantum computation by a sequence of measurements and one-qubit operations. You would be doing one-way measurement quantum computing, and not quantum circuits, but it's just as universal.

I agree with you, but with a couple of corrections. The cheaper algorithm called Density Functional Theory is probably the most popular kind of quantum calculation on molecules, and scales as ~N^2.5 in practice. On the other hand, the number of basis functions is a more than the number of valence electrons in the molecule (if the calculation is at all sane), much larger than the number of atoms. So the exponent is often smaller than you said, but the N is also much bigger. So in the end you're absolutely right about the need for quantum computing for molecules.