  Matter radii of the $^{34-40}$Mg nuclei are investigated by self-consistent
Hartree-Fock-Bogolyubov calculations assuming the axial symmetry. With the
semi-realistic M3Y-P6 interaction, the $N$-dependence of the matter radii
observed in the experiments is reproduced excellently. Both the pairing and the
deformation play significant roles in an intertwined manner. The $^{35}$Mg
nucleus has a smaller radius than the neighboring even-$N$ nuclei, which is
attributed to its smaller deformation. In contrast, a neutron halo is obtained
in $^{37}$Mg. We point out that, in contrast to the pairing anti-halo effect
that may operate on the even-$N$ nuclei, the pair correlation enhances halos in
odd-$N$ nuclei, owing to the new mechanism which we call
\textit{unpaired-particle haloing}. The halo in $^{37}$Mg is predicted to have
peanut shape in its intrinsic state, reflecting $p$-wave contribution, as in
$^{40}$Mg. The $N$-dependence of the deformation is significant again, by which
the single-particle level dominated by the $p$-wave component comes down.
