Changing variables in recurrence relations
It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.

This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. Remember that $T(2^m) = 2T(2^\frac{m}{2}) + m$. Notice that, $S(m/2) = T(2^\frac{m}{2})$. If this particular point is still unclear, let $k =m/2$ and notice all we are doing is this $S(k) = T(2^k)$. Now, we can express $S(m)$ by expanding it to: 
$$ S(m) = 2S(m/2) + m.$$ Solving for $S$ we see that it resolves to our familiar friend $O(m \log m)$.  Now that we've solved $S$ we want to express this in terms of $T(n)$. To do this, merely plug back in our original value for $m$ and we have $T \in O(\log n \log \log n)$.