This is related to problem in graph theory.
OEIS defines A033485 as
$a(1)=1$ and $a(n)=a(n-1)+a(\lfloor n/2 \rfloor)$.
Q1 what are upper bounds and asymptotics for $a(n)$, can we get $\exp(o(n))$?
For real $A,0 < A < 1$ define:
$b(0)=b(1)=1$ and $b(n)=b(n-1)+b(\lfloor A n\rfloor)$
If $A \le \frac12$ then $b(n) \le a(n)$.
Q2 what are upper bounds and asymptotics for $b(n)$?
This recurrence was the subject of one of Donald Knuth's earliest papers! See https://tensen.net/research/static/logos/number-theory/partitions-restricted/knuth.pdf .
Sure, for each fixed $k$ both of them are (up to a constant) eventually dominated by $c(n)=c(n-1)+c(n-k)$ and this sequence is $O(t^n)$ for $t=t(k)\to 1$ as $k\to \infty$ (one has to prove a simple estimate for the roots of $t^k=t^{k-1}+1$).
Set $a_k(1)=r_k$ and $a_k(n)=a_k(n-1)+2^k a_k(\lfloor n/2\rfloor)$ for $n\geq 2$ where $r_0=1$ and $r_k=a_{k-1}(2)=(1+2^{k-1})r_{k-1}\leq 2^kr_{k-1}$.
We have $a_0(n)=a(n)$ for $a(n)$ defined by the OP.
An easy induction shows $a_k(2n),a_k(2n+1)\leq a_{k+1}(n)$.
We get thus $$a(n)=a_0(n)\leq a_1(\lfloor n/2\rfloor)\leq a_2(\lfloor n/4\rfloor)\leq \ldots\leq a_{\lfloor \log_2 n\rfloor}(1)=r_{\lfloor \log_2(n)\rfloor}\ .$$
Using $r_k\leq 2^k r_{k-1}\leq 2^{k+(k-1)}r_{k-2}\leq\ldots$, we get finally $$a(n)\leq 2^{1+2+\ldots+\lfloor\log_2(n)\rfloor}\sim \sqrt{2}^{(\log_2 n)^2}$$ as observed by the OP.
Confirming the numerical evidence, the $b(n)$ sequences have rate of growth $$b(n)=n^{\Theta(\log n)}.$$
On the one hand, since $b(n)$ is nondecreasing, we have $$\begin{align}b(n)&=b(\lfloor An\rfloor)+b(n-1)\\ &\le2b(\lfloor An\rfloor)+b(n-2)\\ &\le\cdots\\ &\le(n-1)b(\lfloor An\rfloor)+b(1)\\ &\le nb(\lfloor An\rfloor). \end{align}$$ Since it takes at most $(\log n)/\log A^{-1}$ iterations of $n\mapsto\lfloor An\rfloor$ to get from $n$ down to $1$, we obtain $$b(n)\le n^{C\log n},\qquad C=(\log A^{-1})^{-1}.$$
On the other hand, we have, say, $$b(n)\ge\frac n2b(\lfloor An/2\rfloor)$$ by the same argument, which easily yields $$b(n)=\Omega(n^{c\log n})$$ for any $c<\frac12\log\frac2A$.
Philippe Dumas has work deriving very precise asymptotic results for 'divide-and-conquor' sequences such as this. For instance, see 'Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated' from 2014 (https://specfun.inria.fr/dumas/Publications/Dumas14.pdf).
