Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?
The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is 
$$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$
and by expanding it, we get 
$$
\begin{align*}
T(n) &amp;= n\log n + \sqrt{n}T(2\sqrt{n}) \\ &amp;=
n\log n + 2n\log (2\sqrt{n}) + 2^{1/2} n^{3/4} T(2^{3/2}n^{1/4}) \\ &amp;=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^{5/4} n^{7/8} T(2^{7/4} n^{1/8}) \\ &amp;=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^3 n \log (2^{7/4} n^{1/8}) + \cdots,
\end{align*}
$$
so each level of the recursion takes time proportional to $n\log n$. Since there are $\log\log n$ levels, we get the quoted running time. For more information, check out these lecture notes.