The "right" answer here is unfortunately most likely a big pile of feature work: some sort of regex or parser/grammar literal in the language, with the compiler able to lower it to an efficient implementation. If you look at the history of, say, JavaScriptCore's regular expression support, you can see a similar thing where they initially called out to a regex library, then slowly implemented "native" support for more and more subsets of regex capabilities, and finally added support for them in their JIT compiler.
But, in the mean time, it's still probably worth profiling the current setup and making sure that we're at least spending the bulk of the time in icu::RegexMatcher, rather than in bridging code. Sadly there's nothing to be done about having to UTF8->UTF16 transcode as long as we use ICU regex support, but hopefully that shouldn't be a major contributor to the time taken now that we're doing bulk access properly. If it is, there's various things we have planned for String to make that somewhat better.