In practical terms, it would behoove you to pre-process the nearly 1 million lines of text ahead of time so you're searching over a much smaller set of possible matches.

If this is a relatively stable corpus of some kind, then there are any number of things you could do - use the commandline grep, throw it in SQLite/MySQL - or even better, Sphinx.

Once you do this, any suggestion you use in this discussion for efficiency in the Perl script itself will work even better for you.