The verification delays grow exponentially with the number of transactions simply because each node must perform it's own series of checks before forwarding said block.
Wrong, because the number of nodes getting involved in verification of specific block grows exponentially as well, so the relationship between number of transactions and propagation time is linear.
As an analogy think about how a bacteria multiplies, at every step a size of the colony increased by factor of 2 until it's reached lets say 1024, if suddenly it requires twice more time to multiple then it takes only twice longer to reach the size of 1024 because the number of multiplication steps is still the same.
If block verification were a distributable process, you'd be correct, but it isn't. At least it's not now, and I don't know how it could be done. One thing that could be altered to speed up propagation is for some nodes to have trusted peers, wherein if they receive a block from that peer, they re-broadcast that block first then do their checks. But if this was the default behavior, the network could be DDOS'ed with false blocks.