In this paper, we first establish well-posedness of McKean-Vlasov stochastic differential equations (McKean-Vlasov SDEs) with common noise, possibly with coefficients having super-linear growth in the state variable. Second, we present stable time-stepping schemes for this class of McKean-Vlasov SDEs. Specifically, we propose an explicit tamed Euler and tamed Milstein scheme for an interacting particle system associated with the McKean-Vlasov equation. We prove stability and strong convergence of order $1/2$ and $1$, respectively. To obtain our main results, we employ techniques from calculus on the Wasserstein space. The proof for the strong convergence of the tamed Milstein scheme only requires the coefficients to be once continuously differentiable in the state and measure component. To demonstrate our theoretical findings, we present several numerical examples, including mean-field versions of the stochastic $3/2$ volatility model and the stochastic double well dynamics with multiplicative noise.