In this paper we study optimal stopping problems for nonlinear Markov processes driven by a McKean-Vlasov SDE and aim at solving them numerically by Monte Carlo. To this end we propose a novel regression algorithm based on the corresponding particle system and prove its convergence. The proof of convergence is based on perturbation analysis of a related linear regression problem. The performance of the proposed algorithms is illustrated by a numerical example.