Why is hierarchical clustering quadratic and k-means linear?
I think these time complexities are optimistic cases, but apart from that I think the reason is that in hierarchical clustering you consider the distances between many, if not all pairs of data points. The number of pairs scales quadratically with the number of points.

For k-means you somewhat cheat your way around considering all pairs by looking at the distances between each data point and the k means only. This scales linearly in both k and the number of data points.

So I think the speed up is caused by using the distance to the means as proxy for the distances between all points.