If $\gcd(a-1,m)=1$, then there will be no problems using the sum formula for a geometric series. Otherwise I suggest the following that is kind of like the square-and-multiply approach to modular exponentiation.
Write $q=1/a$ (= the modular inverse of $a$) and denote the geometric sum by $ S(k)=\sum_{i=0}^{k-1} q^i.\qquad\text{<- Edit: A typo here. The upper bound was off by one.} $ Then we have the length-doubling recurrence relation (all arithmetic done modulo $m$, so if you are so minded, imagine $\%m$ at the end of each addition or product - I prefer to think of this as doing arithmetic in the ring $\mathbb{Z}/m\mathbb{Z}$): $ S(2k)=S(k)(1+q^k), $ as well as the add-one recurrence: $ S(k+1)=q S(k) +1. $
With the aid of these you can follow the usual square-and-multiply (or rather, double-and-add) logic. So for example to calculate $S(113)$ you need to first calculate $S(112)$ and then apply the add-one -formula. To calculate $S(112)$ you first calculate $S(56)$, and then apply the length-doubling -formula. Apply these ideas recursively.
The complexity looks like to be of the order $O\left((\log_2n)^2\right)$ modular multiplications given that you need to compute all those $q^k$:s for the length doubling formula. It does look like, there is a lot of redundancy there (in that the $q^k$ you will need in the next recursive call has probably already been computed). I'm sure you can build a more efficient recursive procedure from these elements, as it is possible to predetermine exactly which powers $q^k$ are needed! May be what you end up with has linear complexity (in terms of the number of bits in $n$ using the cost of a modular multiplication as a unit)?
Some further shaving may be possible by reorganizing the calculation further.