The answer to your question is, essentially, yes. The use of birthday paradox algorithms in the second stage of ECM is standard, and this can be done space efficiently using a random walk approach. The usual Pollard rho algorithm requires some minor modifications (using a slightly different choice of random walk, as you suggested), which are described in detail in section 6 of Brent's 1986 paper Some integer factorization algorithms using elliptic curves.

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), 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})$.