I found a recurrence of a similar form on this forum, but I couldn't use it to gain any intuition for my question. So far, I've tried 3 things. I've tried unrolling it but could not really see a pattern. I've tried transforming it in hopes that I would be able to use Master's Theorem, but no such luck. I've also tried to guess a complexity and apply induction to see if I can simplify it but I haven't been able to reach a tight bound.
EDIT: Assume that $T(n)$ is constant for $n \leqslant 3$
Best Answer
Use the variable change:
$\begin{align*} n &= 2 \cdot 2^{2^k} \\ k &= \log_2 \left(\log_2 \frac{n}{2}\right) \\ \sqrt{2 n} &= \sqrt{2 \cdot 2 \cdot 2^{2^k}} \\ &= 2 \cdot 2^{2^{k - 1}} \\ \sqrt{n} &= \sqrt{2} \cdot 2^{2^{k - 1}} \\ t(k) &= T(2 \cdot 2^{2^k}) \end{align*}$
We get the nice (?) recurrence:
$\begin{align*} t(k) &= 2 \cdot 2^{2^{k - 1}} t(k - 1) + \sqrt{2} \cdot 2^{k - 1} \\ \end{align*}$
(it is nice in that it is a linear recurrence of first order thus solvable).
Divide through by $2^k \cdot 2^{2^k}$, simplify,
$\begin{align*} \frac{t(k)}{2^k \cdot 2^{2^k}} - \frac{t(k - 1)}{2^{k - 1} \cdot 2^{2^{k - 1}}} &= \frac{\sqrt{2}}{2^k \cdot 2^{2^{k - 1}}} \end{align*}$
Sum over $1 \le k \le r$, the left hand side telescopes nicely:
$\begin{align*} \frac{t(r)}{2^r \cdot 2^{2^r}} - \frac{t(0)}{2^0 \cdot 2^{2^0}} &= \sum_{1 \le k \le r} \frac{\sqrt{2}}{2^k \cdot 2^{2^{k - 1}}} \\ t(r) &= 2^{r - 1} \cdot 2^{2^r} t(0) + \sqrt{2} \cdot 2^r \cdot 2^{2^r} \cdot \sum_{1 \le k \le r} 2^{-k} \cdot 2^{-2^{k - 1}} \end{align*}$
We get a (very crude) upper bound on the sum by:
$\begin{align*} \sum_{1 \le k \le r} 2^{-k} \cdot 2^{-2^{k - 1}} &\le \sum_{1 \le k \le r} 2^{-k} \\ &< \sum_{k \ge 1} 2^{-k} \\ &= \frac{1}{2} \end{align*}$
This gives the bound:
$\begin{align*} t(r) &\le 2^{r - 1} \cdot 2^{2^r} t(0) + \sqrt{2} \cdot 2^{r - 1} \cdot 2^{2^r} \end{align*}$
A matching lower bound is given by the sum being larger than 0.
This means (throw in a constant to simplify):
$\begin{align*} t(r) &= \Theta\left(2^r \cdot 2 \cdot 2^{2^r}\right) \\ T(n) &= \Theta\left(2^{\log_2 \log_2 n} \cdot n\right) \\ &= \Theta(n \log n) \end{align*}$
Phew!