Make sure you aren't using the -l flag.

Is this output going to the terminal screen? That's the only way \r is going to work, since "mystuff\rOVERWRITE" is what is actually written, and it depends on the terminal to interpret \r as carriage return.

If you are outputing to a pipe or a file, you are out of luck, unless you use some utility that formats things as if it were a terminal screen (I think I've seen such a beast), or you intercept the output with a tied filehandle or an io layer that interprets things for you.