The misconception isn't exactly that quantum computers speed up computations by parallelism. They kinda do. The trouble is that what they do isn't anything so simple as "try all the possibilities and report on whichever one works" -- and the real difference between that and what they can actually do is in the reporting rather than the trying.
Of course that means that useful quantum algorithms don't look like "try all the possibilities", but they can still be viewed as working by parallelism. For instance, Grover's search algorithm starts off with the system in a superposition that's symmetrical between all the possibilities, and each step changes all those amplitudes in a way that favours the one we're looking for.
For the avoidance of doubt, I'm not in any way disagreeing with Scott Aaronson here: The naive conception of quantum computation as "just like parallel processing, but the other processors are in other universes" is too naive and leads people to terribly overoptimistic expectations of what quantum computers can do. I just think "quantum computers don't speed up computations by parallelism" is maybe too simple in the other direction.
[EDITED to remove a spurious "not"]
They kinda do.
I agree that "parallelism but in other universes" is a weird phrasing.
What happens with quantum computation is cancellation due to having negative probabilities. The closest classical analogue seems to me to be dynamic programming, not parallel programming -- you have a seemingly large search space that in fact can be made to reduce into a smaller search space by e.g. cleverly caching things. In other words, this is about how the math of the search space works out.
If your parallelism relies on invoking MWI, then it's not "real" parallelism because MWI is observationally indistinguishable from other stories where there aren't parallel worlds.
Another month, another rationality quotes thread. The rules are: