Brent's paper *[Some integer factorization algorithms using elliptic curves][1]* 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), however it is not space efficient. Cycle detection techniques do not apply because the iteration function used is not a deterministic operation on the elliptic curve modulo any of the (unknown) prime factors of $n$, and it is not 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, which can be recognized using standard techniques (e.g. Floyd's algorithm) with a space complexity of $O(\log n)$ bits.  But the expected length of this cycle (assuming this iteration function actually approximates a random walk) is $O(\sqrt{m})$, where $m$ is the order of $P$ on $E(\mathbb{Z}/n\mathbb{Z})$, not $O(\sqrt{r})$.

  [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.126.5687