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.