Being able to calculate the derivative is very useful (the backprop rule, etc.). However it isn't actually necessary here, since you can approximate the slope by just sampling points nearly. Strict differentiability isn't the crucial property here, but it does make things faster.

What is, I think, is that the error function is continuous and there is a monotonic path of improvement from most of the space to good solutions in it. Then you can just descend in the error function until you reach it.

We don't really understand why that happens in deep learning, that is, why the error functions of deep neural networks tend to not have complex shapes with local minima that you can get stuck in. This is currently being investigated.

This also isn't a problem limited to deep learning. In evolution, the same is true - we are limited to small local improvements, but over large amounts of time nature arrives at amazingly efficient solutions. That suggests that the fitness function space over genomes is also, to some extent, continuous and allows monotonic improvement. Again, we don't really know why, yet.