MNT Curves
First we walk through the construction of $k=6$ MNT curves. Set $q = l^2 + 1 , t = \pm l + 1$. Then it turns out $q + 1  t$ divides $q^6  1$.
The CM equation becomes $D V^2 = 3 l^2 \pm 2 l + 3$. If we write $U = 3l \pm 1$ we have an easily solved generalized Pell equation
Summary:

Pick a $D$ not too large and solve the equation
\[ D V^2 = 3 l^2 \pm 2 l + 3 \]for +++$V, l$+++

Check $q = l^2 + 1$ is prime

Check $q  t + 1 = q \pm l$ has a large prime factor

Check the embedding degree is not less than 6 (very likely)

Use CM method to construct the curve
We can explain how the $k=6$ case works using cyclotomic polynomials. Recall that $\Phi_6(l) = l^2  l + 1$, and that $\Phi_6(l)  l^6  1$. Then if the plus sign is chosen in the above example, $q = \Phi_6(l) + l$, and the order of the curve is $n = q  t + 1 = \Phi_6(l)$. Thus
and since $n  l^6  1$ we have $n  q^6  1$ hence the embedding degree is indeed 6 by the BK theorem.
If the minus sign is chosen instead, we have $q = \Phi_3(l)  l$, $t = l + 1$, (recall $\Phi_3(l) = l^2 + l + 1$) which means the order of the curve is $n = \Phi_3(l)$. Hence
and since $\Phi_3(l)  l^6  1$ we have that the embedding degree of the curve is 6. Of course $\Phi_3(l)$ also divides $l^3  1$ but in general this is not congruent to $(l)^3  1$ so the embedding degree is not 3.
Note that $q$ can only be odd in the above cases if $l$ is even which is why the MNT paper uses $2l$ instead of our $l$, which gives $q = 4l^2+1, t = 1 \pm 2l$. So if the above Pelltype equation is used, a solution $U$ is useful only if $U = 1, 5 \pmod{6}$.
The $k=4$ case from the MNT paper can also be explained in terms of cyclotomic polynomials. Recall $\Phi_4(l) = l^2 + 1$. Then taking $q = \Phi_4(l) \pm l$ and $t = \pm l + 1$ so that $n = \Phi_4(l)$ yields
hence $n  q^4  1$. When the minus sign is chosen, and the variable $l$ is replaced by $l+1$ we match the parametrizations of the MNT paper exactly.
For $k=3$, the MNT paper gives $q = 3l^2  1$, $t=1\pm 3l$ for even $l$, but it is not obvious how these are related to cyclotomic polynomials.
Note the MNT paper goes further: it shows that aside from supersingular curves, these are the only parametrizations that lead to embedding degrees $3, 4$ and $6$.