Thanks, I like this answer.
While talk of the halting problem further down is interesting, I have a real world situation now where users are putting out bad regex on production servers. The regex they have access ltoo is actualy not Perl, but a very limited subset of Java's regex. It has .* though and they manage to shoot themselves in the foot with abundant use of .* I don't really need 100% accurate count of how many steps they are taking, just an idea if they are in the region of up to a few hundred steps per line, or way beyond it. If they breach some arbitrary limit we will ask them to come to us for regex guidance. So counting the lines from a re debug will be close enough for my purpose.
Pereant, qui ante nos nostra dixerunt!