The answer to your question is, essentially
Brent's paper Some integer factorization algorithms using elliptic curves describes a "birthday paradox" ECM extension based on a random walk that only uses $O(\sqrt{r})$ group operations on the elliptic curve (see Section 6), yeshowever it is not space efficient. The use Cycle detection techniques do not apply because the iteration function used is not a deterministic operation on the elliptic curve modulo any of birthday paradox algorithms in the second stage (unknown) prime factors of ECM $n$, and it is standardnot clear how one might construct such a function.
One can apply the usual Pollard-$\rho$ approach to computations on the elliptic curve performed mod $n$, say using an iteration function where $Q_{i+1}$ is $2Q_i$ or $2Q_i+Q$, depending on the parity of the $x$-coordinate of $Q_i$ when viewed as an integer in $[0,n-1]$. This will eventually lead to a cycle, and this which can be done space efficiently recognized using standard techniques (e.g. Floyd's algorithm) with a random walk approachspace complexity of $O(\log n)$ bits. The usual Pollard rho algorithm requires some minor modifications But the expected length of this cycle (using assuming this iteration function actually approximates a slightly different choice of random walk, as you suggested), which are described in detail in section 6 ) is $O(\sqrt{m})$, where $m$ is the order of Brent's 1986 paper Some integer factorization algorithms using elliptic curves.$P$ on $E(\mathbb{Z}/n\mathbb{Z})$, not $O(\sqrt{r})$.
