The performance of regexp is an order of magnitude slower than the same functionality in strfind.  Some performance penalty is expected, but not this great.

Sample Code:

octave:71> xc = cellstr (char (randi( [65 65+25], [1e5, 20])));
octave:72> tic; yr = regexp (xc, 'ABC'); toc
Elapsed time is 2.5726881 seconds.
octave:73> tic; y = strfind (xc, 'ABC'); toc
Elapsed time is 0.20126295 seconds.

There seem to be several causes.  It appears that Octave is re-compiling the PCRE pattern every time it does a match for one row.  Octave is also bothering to process and restore all possible return values (start, end, tokens, tokenextents, match, and splits) even if only a subsection is desired.  I haven't done a hotspot analysis though.