Like
tadman++ noted the problem is that once you use it,
all regexes anywhere in the script become slower - not likely to be tolerable in the context of the Everything engine.. And this one in particular is pretty simple:
$title =~ s{((?:Re: ){2,})}{"Re(" . length($1)/4 . "): "}ge;
Works a treat for your test cases.
Makeshifts last the longest.