The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm
As you mention, the costliest step is computing $a^M \bmod{n}$. This is done using the repeated squaring algorithm. Each squaring or multiplication modulo $n$ takes time $M(n)$, where $M(n)$ is the time complexity of multiplication.

We can estimate the number of multiplications by
$$
\sum_{\text{prime } q \leq B} \frac{\log B}{\log q} \cdot \log q &lt; \pi(B) \log B = O(B).
$$
This improves slightly on the Wikipedia estimate of $O(B\log B)$.

The school multiplication algorithm takes time $O(\log^2 n)$, which is how Wikipedia got that factor. But nowadays faster algorithms are known, which run in time $\tilde{O}(\log n)$. So a better estimate on the complexity is $\tilde{O}(B\log n)$.