There is another closely related recurrence that admits an exact
solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives
$T(1)=1$)
$$T(n) = 2 T(\lfloor n/4 \rfloor) + \lfloor \sqrt{n} \rfloor.$$
Furthermore let the base four representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$
Then we can unroll the recurrence to obtain the following exact
formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j\Bigg\lfloor
\sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}}
\Bigg\rfloor.$$
Now to get an upper bound consider a string of digits with value three
to obtain
$$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} 3\times 4^{k-j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j} -1}
\\ < \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
\sqrt{4^{\lfloor \log_4 n \rfloor +1}}
\\ = (\lfloor \log_4 n \rfloor + 1) \times
2^{\lfloor \log_4 n \rfloor +1}.$$
This bound is actually attained and cannot be improved upon, just like
the lower bound, which occurs with a one digit followed by zeroes to
give
$$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor-j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
\sqrt{4^{\lfloor \log_4 n \rfloor}}
\\ = (\lfloor \log_4 n \rfloor + 1) \times
2^{\lfloor \log_4 n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\lfloor \log_4 n \rfloor \times
2^{\lfloor \log_4 n \rfloor}
\in \Theta\left(\log_4 n \times 4^{1/2 \log_4 n}\right)
= \Theta\left(\log n \times \sqrt{n}\right).$$
Observe that there is a lower order term
$$2^{\lfloor \log_4 n \rfloor}
\in \Theta\left(4^{1/2 \log_4 n}\right)
= \Theta\left(\sqrt{n}\right).$$
The above is in agreement with what the Master theorem would produce.
Addendum Nov 3 2014. The lower bound is missing a lower order term,
which is $-(2^{\lfloor \log_4 n \rfloor+1}-1)$ the same as was done at this
MSE link.
Here is another computation in the same spirit:
MSE link.