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.
As proved in this answer, if we represent $n$ as $n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_m+1}))\dots)$ with $t_j\geq 0$, then
\begin{split}
a(n) = P(\ell)^{t_1}\prod_{j=1}^{\ell-1} P(\ell-j)^{t_{2j}+t_{2j+1}+1},
\end{split}
where $\ell:=\left\lfloor\frac{m+1}2\right\rfloor$ and
$$P(k) := q^k+p\frac{q^k-1}{q-1}.$$
Notice that this does not depend on $t_m$ when $m$ is even.
Grouping the summands in $s(n)$ by the number of unit bits (very much like in this other answer), for $n\geq 1$ we have
\begin{split}
s(n) &= \sum_{m=1}^n\ \sum_{t_1+t_2+\dots+t_{m}=n-m}\ P(\lfloor(m+1)/2\rfloor)^{t_1} \prod_{j=1}^{\lfloor(m-1)/2\rfloor} P(\lfloor(m+1)/2\rfloor-j)^{t_{2j}+t_{2j+1}+1}\\
&= \sum_{m=1}^n\ [x^{n-m}]\ \frac1{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}\cdot\frac{1+\frac{(-1)^m-1}2x}{1-x}\\
&= [x^n]\ \sum_{m=1}^\infty\ \frac{x^m}{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}\cdot\frac{1+\frac{(-1)^m-1}2x}{1-x}.
\end{split}
That is, the generating function for $s(n)$ is
$$\sum_{n\geq 0} s(n)x^n = 1+\frac1{1-x}\sum_{m=1}^\infty\ \frac{x^m(1+\frac{(-1)^m-1}2x)}{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}.$$
Combining terms for $m=2k-1$ and $m=2k$, we can rewrite it as
$$\sum_{n\geq 0} s(n)x^n = 1+\frac{1}{1-x}\sum_{k=1}^\infty\ \frac{x^{2k-1}}{1-P(k)x}\cdot\prod_{j=1}^{k-1} \frac{P(j)}{(1-P(j)x)^2},$$
which is quite close to the conjectured formula.
Best Answer
First, we let $P(j,k):=1+f(\lfloor\tfrac{j}{2^k}\rfloor+1)$ and sum over $n$ of fixed weight $\ell:=\mathrm{wt}(n)$ (like in this answer): \begin{split} s(n) &= \sum_{\ell=0}^n \sum_{t_1 + \dots + t_\ell \leq n-\ell} \sum_{j=0}^{2^\ell-1} (-1)^{\ell-\mathrm{wt}(j)} \prod_{k=0}^{\ell-1} P(j,k)^{t_k+1} \\ &= [x^{n+1}]\ \sum_{\ell=0}^n \sum_{j=0}^{2^\ell-1} (-1)^{\mathrm{wt}(j)+1} \prod_{k=0}^{\ell} \frac{-P(j,k)x}{1-xP(j,k)}. \end{split}
Now, we notice that $P(j,k)$ depends on runs of unit bits in $j$. Namely, each run of length $u-1$ contributes the term $$\prod_{v=1}^{u} \frac{-vx}{1-vx} = x^{u} (-1)^{u} u! \prod_{v=1}^{u} \frac1{1-vx}.$$ Hence, introducing the number $z$ of zero bits in $j$ padded with an extra zero at the beginning (and so $\mathrm{wt}(j)=\ell+1-z$), we have \begin{split} s(n) &= [x^{n+1}]\ \sum_{\ell=0}^n [y^{\ell+1}]\ \sum_{z\geq 0} (-1)^{\ell+2-z} \left(\sum_{u\geq 1} y^u (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^z\\ &= -[x^{n+1}]\ \sum_{\ell=0}^n (-1)^{\ell+1} [y^{\ell+1}]\ \left(1+\sum_{u\geq 1} y^{u} (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \sum_{m\geq 0} S(m,u) x^{m-u}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{m\geq 1} x^m B_m^o\right)^{-1}, \end{split} which can be recognized as INVERTi transform of ordered Bell numbers $B_m^o$.