We develop an explicit Milstein-type scheme for McKean-Vlasov stochastic differential equations using the notion of derivative with respect to measure introduced by Lions and discussed in \cite{cardaliaguet2013}. The drift coefficient is allowed to grow super-linearly in the space variable. Further, both drift and diffusion coefficients are assumed to be only once differentiable in variables corresponding to space and measure. The rate of strong convergence is shown to be equal to $1.0$ without using Itô's formula for functions depending on measure. The challenges arising due to the dependence of coefficients on measure are tackled and our findings are consistent with the analogous results for stochastic differential equations.