We investigate the effect of correlated disorder on Majorana zero modes (MZMs) bound to magnetic vortices in two-dimensional topological superconductors. By starting from a lattice model of interacting fermions with a $p_x pm i p_y$ superconducting ground state in the disorder-free limit, we use perturbation theory to describe the enhancement of the Majorana localization length at weak disorder and a self-consistent numerical solution to understand the breakdown of the MZMs at strong disorder. We find that correlated disorder has a much stronger effect on the MZMs than uncorrelated disorder and that it is most detrimental if the disorder correlation length $ell$ is on the same order as the superconducting coherence length $xi$. In contrast, MZMs can survive stronger disorder for $ell ll xi$ as random variations cancel each other within the length scale of $xi$, while an MZM may survive up to very strong disorder for $ell gg xi$ if it is located in a favorable domain of the given disorder realization.