Experimenting with a CAS suggests an induction. In order to handle the induction, we need to consider the forms of the numbers involved. $\frac{4^m-1}{3} = 1 + 2^2 + 2^4 + \cdots + 2^{2m-2}$ alternates $1$ and $0$ bits. The map $2n + 1 \to n - 2^{f(n)}$ drops the rightmost bit (which is $1$) and clears the next least significant bit. The map $2n \to n$ drops the rightmost bit (which is $0$). And the map $2n \to 2n - 2^{f(n)}$ moves the least significant bit right one place. So the numbers which occur in the evaluation tree of $\frac{4^m-1}{3}$ are of the form $2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k}$ where $i \le j - 2$ and $k \ge 0$; and (when we get down to one bit) the form $2^i$.
Starting with the simplest case, when $i > 0$, $a(2^i) = pa(2^{i-1}) + qa(2^{i-1})$ so by induction $a(2^i) = (p+q)^i$.
For the more general case, let $A(i,j,k) = a(2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k})$ subject to the aforementioned constraints on $i,j,k$.
For $i > 0$, we have an even argument and use the second case of the recursion:
\begin{eqnarray*}
A(i,j,k) &=& a(2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
&=& pa(2^{i-1} + 2^{j-1} + 2^{j+1} + \cdots + 2^{j+2k-1}) + qa(2^{i-1} + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
&=& pA(i-1, j-1, k) + qA(i-1, j, k)
\end{eqnarray*}
Then it's a trivial proof by induction that $$A(i,j,k) = \sum_{u=0}^i \binom{i}{u} p^u q^{i-u} A(0, j-u, k)$$
For $i = 0$, we have an odd argument and use the third case of the recursion:
\begin{eqnarray*}
A(0,j,k) &=& a(1 + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
&=& a(2^{j+1} + \cdots + 2^{j+1+2(k-1)}) \\
&=& \begin{cases}
a(0) & \textrm{if } k=0 \\
a(2^{j+1}) & \textrm{if } k=1 \\
A(j+1, j+3, k-2) & \textrm{otherwise}
\end{cases} \\
&=& \begin{cases}
1 & \textrm{if } k=0 \\
(p+q)^{j+1} & \textrm{if } k=1 \\
\sum_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, k-2) & \textrm{otherwise}
\end{cases}
\end{eqnarray*}
Further CAS experimentation suggests that the theorem we need to prove is $$A(0, j, 2v-1) = A(0, j, 2v) = \left(p\frac{q^v-1}{q-1} + q^v\right)^{j+1} A(0, 2, 2v-2)$$
The first of those equalities is easy: $$A(0,j,2) = \sum_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, 0) = \sum_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} = (p+q)^{j+1}$$ so $A(0,j,1) = A(0,j,2)$ and since the only occurrence of $k$ in the third case is in the parameter $k-2$ the rest follows by induction on $v$.
The second equality is the interesting one. Again, by induction on $v$:
\begin{eqnarray*}
A(0,j,2v) &=& \sum_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, 2v-2) \\
&=& \sum_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} \left(p\frac{q^{v-1}-1}{q-1} + q^{v-1}\right)^{j+4-u} A(0, 2, 2v-4) \\
&=& \left[ \sum_{u=0}^{j+1} \binom{j+1}{u} p^u \left(pq\frac{q^{v-1}-1}{q-1} + q^v\right)^{j+1-u} \right] \color{Blue}{\left(p\frac{q^{v-1}-1}{q-1} + q^{v-1}\right)^3 A(0, 2, 2v-4)} \\
&=& \left( p + pq\frac{q^{v-1}-1}{q-1} + q^v \right)^{j+1} \color{Blue}{A(0, 2, 2v-2)} \\
&=& \left(p\frac{q^v-1}{q-1} + q^v\right)^{j+1} A(0, 2, 2v-2)
\end{eqnarray*}
as desired.
The answer to the original question now drops out: $a\left(\tfrac{4^m-1}{3}\right) = A(0, 2, m-2)$, but $A(0, 2, k)$ has the form of a cube times $A(0, 2, k-2)$ so by induction it's always a cube.
Let $n=m^tk$ where $m\nmid k$. Then $f(n)=m^t$.
Furthermore, if $t>0$, then $f(n/m)=m^{t-1}$ and $n-f(n/m)=m^{t-1}(mk-1)$. It follows that $a(n)=a(m^{t-1}k)+a(m^{t-1}(mk-1))$ and further by induction on $t$,
$$
(\star)\qquad a(n)=\sum_{i=0}^t \binom{t}{i} a\big(m^ik-\frac{m^i-1}{m-1}\big).
$$
CASE $m>2$. In this case, formula $(\star)$ reduces to
$$a(n) = a(k)+(2^t-1)a(k-1).$$
Let's analyze $s(n)$.
It is clear that for any $\ell\not\equiv 0\pmod{m}$, we have
$$\sum_{k=0\atop k\equiv \ell\pmod{m}}^{m^n-1} a(k) = s(n-1)$$
and correspondingly
$$\sum_{k=0\atop k\equiv 0\pmod{m}}^{m^n-1} a(k) = s(n) - (m-1)s(n-1)$$
Now we are ready to derive a recurrence for $s(n)$ by grouping the summation indices based on the power $m^t$ they contain:
\begin{split}
s(n) &= 1 + \sum_{t=0}^{n-1} \sum_{k=1\atop k\not\equiv 0\pmod{m}}^{m^{n-t}-1} \left(a(k) + (2^t-1)a(k-1)\right) \\
&=1 +\sum_{t=0}^{n-1} \left((m-1)s(n-t-1) + (2^t-1)((m-2)s(n-t-1) + s(n-t)-(m-1)s(n-t-1))\right) \\
&=1 +\sum_{t=0}^{n-1} \left((m-2^t)s(n-t-1) + (2^t-1)s(n-t)\right) \\
&=2 - 2^n + \sum_{t=1}^n (2^{t-1}+m-1)s(n-t).
\end{split}
Restating the above recurrence in terms of the generating function $S(x):=\sum_{n\geq 0} s(n)x^n$, we have
$$S(x) = \frac{2}{1-x} - \frac{1}{1-2x} + \left(\frac{x}{1-2x} + \frac{(m-1)x}{1-x}\right)S(x).$$
That is,
$$S(x) = \frac{1-3x}{1 - (m+3)x + (2m+1)x^2},$$
from where the required recurrence follows instantly.
CASE $m=2$. In this case, formula $(\star)$ takes form:
$$a(n)=a(k)+\sum_{i=1}^t \binom{t}{i} a(2^{i-1}(k-1)).$$
It further follows that for $n=2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)$ with $t_j\geq 0$, we have
\begin{split}
a(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2+i_1} \binom{t_2+i_1}{i_2} \sum_{i_3=0}^{t_3+i_2} \dots \sum_{i_\ell=0}^{t_\ell+i_{\ell-1}} \binom{t_\ell+i_{\ell-1}}{i_\ell} \\
&=\prod_{j=1}^\ell (\ell+2-j)^{t_j}.
\end{split}
Grouping the summands in $s(n)$ by the number of unit bits, we have
\begin{split}
s(n) &= \sum_{\ell=0}^n\ \sum_{t_1+t_2+\dots+t_{\ell}\leq n-\ell}\ \prod_{j=1}^\ell (\ell+2-j)^{t_j}\\
&= \sum_{\ell=0}^n\ \sum_{t_1+t_2+\dots+t_{\ell}+t_{\ell+1} = n-\ell}\ \prod_{j=1}^{\ell+1} (\ell+2-j)^{t_j}\\
&=\sum_{\ell=0}^n [x^{n-\ell}]\ \prod_{j=1}^{\ell+1} \frac1{1-jx} \\
&=\sum_{\ell=0}^n S(n+1,\ell+1) \\
&=B_{n+1},
\end{split}
where $S(n+1,\ell+1)$ are Stirling numbers of second kind, and $B_{n+1}$ is Bell number.
Best Answer
Let me address the case of $s_2(n)$.
First we notice that $g(n-1) = k$ whenever $n=(2k+1)2^t$. Then for $n=2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)>1$ with $t_j\geq 0$, we have
$$a_2(n) = \begin{cases} a_2\bigg(2^{t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) + a_2\bigg(2^{t_3}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) & \text{if}\ t_1=0; \\ a_2\bigg(2^{t_1-1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) + a_2\bigg(2^{t_1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)\bigg) & \text{if}\ t_1>0. \end{cases} $$ In contrast to previous questions by the OP, obtaining an explicit formula for $a_2(n)$ here seems to be quite challenging. Still, thanks to the connection $$s_2(n) = \sum_{\ell=0}^n \sum_{t_1+\dots+t_\ell\leq n-\ell} a_2\bigg( 2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots) \bigg),$$ we can translate the above recurrences over to $s_2(n)$.
Let's partition $s_2(n)$ into smaller sums depending on the 2-adic valuation of the summands: $$s_2(n) = \sum_{k\geq 0} s^{(k)}_2(n),$$ where $$s^{(k)}_2(n) := \sum_{j=0\atop \nu_2(2^n+j)=k}^{2^n-1} a_2(j).$$
From the recurrence above, it follows that for $n>1$, $$s_2^{(0)}(n) = \sum_{t=0}^{n-1} s_2(t) = s_2(n-1) + s_2^{(0)}(n-1) = 2s_2^{(0)}(n-1) + \sum_{k\geq 1} s^{(k)}_2(n-1) $$ and for $k>0$ $$s_2^{(k)}(n) = \sum_{m\geq k-1} s_2^{(m)}(n-1).$$ That is, in the matrix form we have: $$ \begin{bmatrix} s_2^{(0)}(n)\\ s_2^{(1)}(n)\\ s_2^{(2)}(n) \\ \vdots \end{bmatrix} = M\cdot \begin{bmatrix} s_2^{(0)}(n-1)\\ s_2^{(1)}(n-1)\\ s_2^{(2)}(n-1) \\ \vdots \end{bmatrix} = M^{n-1}\cdot \begin{bmatrix} 1\\ 1\\ 0\\ 0\\ \vdots \end{bmatrix} $$ where $$M: = \begin{bmatrix} 2 & 1 & 1 & 1 & \\ 1 & 1 & 1 & 1 & \ddots \\ 0 & 1 & 1 & 1 & \ddots \\ 0 & 0 & 1 & 1 & \ddots \\ & \ddots & \ddots & \ddots & \ddots \\ \end{bmatrix}.$$
By induction on $n$ it can be verified that the generating functions for sequences $\big(s_2^{(k)}(n)\big)_{n\geq 0}$ are expressed in terms of the one for Catalan numbers $C(x):=\frac{1-\sqrt{1-4x}}{2x}$ as follows: $$\sum_{n\geq 0} s_2^{(k)}(n)\cdot x^n = (1-x) x^k C(x)^{k+2},$$ or in other words: $$s_2^{(k)}(n) = \frac{k+2}{n+2}\binom{2n-k+1}{n-k} - \frac{k+2}{n+1}\binom{2n-k-1}{n-k-1}.$$
Summing the above generating functions over $k\geq 0$ yields: $$\sum_{n\geq 0} s_2(n)\cdot x^n = \frac{(1-x)C(x)^2}{1-xC(x)} = \frac{(1-x)^2C(x) - 1 + x}{x^2},$$ proving the conjecture for $s_2(n)$.