Let $A(x)$ denote the formal generating function of $\{ a_n\}$. The recurrence relation can be written as $A(x)=e^x A(x^2)$. Applying this repeatedly, we find $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$, where $f(x) = \sum_{i \ge 0} x^{2^i}$.

Asymptotics of $[x^n] e^{P(x)}$ where $P$ is a polynomial with positive coefficients are "easy", for example they follow by Hayman's method, see this paper of [Odlyzko and Richmond][1], and [this paper of Wilf][2] for a worked out example.

As Jeffery remarked, since $a_n \ge [x^n] e^{P_m(x)}$ where $P_m(x) = \sum_{i \le m} x^{2^i}$ for any $m$, this method provides you lower bounds.

As for upper bounds - since $[x^n] e^{f(x)} \le [x^n] e^{\frac{x}{1-x}}$ and $e^{\frac{x}{1-x}}$ is Hayman-admissible (see [page 90 here][3]), Hayman method applies again.

I won't be surprised if $e^{f(x)}$ is already Hayman-admissible, but working out the asymptotics via this method requires one to approximate the solution to the equation $\sum_{i \ge 0} t^{2^i} 2^i=n$ ($0<t<1$) for each $n$, which is not easy to do uniformly for all $n$.


  [1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.243&rep=rep1&type=pdf
  [2]: https://www.math.upenn.edu/~wilf/website/Asymptotics%20of%20exp(P(z)).pdf
  [3]: http://www.dsi.unifi.it/~resp/Handbook.pdf