OK. Here's what I think I maybe've got:
Let G be the random graph G(n,M) on n vertices and M edges. Then RS(G) = O(M*\delta(G)).
Proof (outline): Set the implied constant in the big-O notation as k, to be determined later.
Base Case: M = 0; trivial.
For M>0, choose a vertex v with degree \delta(G), and remove an edge incident to it to obtain the graph G'. Then, by the IH, RS(G') \leq k*(M-1)*(\delta(G)-1) = k*M*\delta(G)-(kM+k\delta(G)-1). For suitable k (I suspect), the probability that there exists some number in [0, kM+k\delta(G)-1] which we can add to the label on v so that the labeling remains range-relaxed graceful is 1.
...Yeah. I guess I hope that this is workable? I dunno though. Eh.