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$, \begin{split} a(n)&=\sum_{i=0}^t \binom{t}{i} a\big(m^ik-\frac{m^i-1}{m-1}\big)\\ &=a(k)+(2^t-1)a(k-1). \end{split}
In particular, if $k\not\equiv 1\pmod{m}$, we have $a(n)=2^ta(k)$.
Now, 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 values of $n$ based on the power $m^t$ they contain: \begin{split} s(n) &= (m-1)s(n-1) + 1 + \sum_{t=1}^{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) \\ &=(m-1)s(n-1) + 1 +\sum_{t=1}^{n-1} (m-1)s(n-t-1) + (2^t-1)((m-2)s(n-t-1) + s(n-t)-(m-1)s(n-t-1)) \\ &=(m-1)s(n-1) + 1 +\sum_{t=1}^{n-1} (m-2^t)s(n-t-1) + (2^t-1)s(n-t) \\ &=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.