My guess would be that key length scales the quantum algorithm time much less than it scales the possibilities. Like, as key length squares, execution time doubles.

I don't know. It's seems crazy that an algorithm wouldn't be affected at all by significant numerical increases.