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.