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\).