Some possibly mutually exclusive suggestions.

• You're not parsing HTML at all. That's good, because that would just slow you down.
• Try with $| off. I don't expect it'll make a difference either way. Notice that $| = 1 won't get the data out of Google any faster, so maybe it doesn't do quite what you think.
• When you find the matching line, last out of the loop.
• Don't split your big string at all. Just run the regexp against it.
• Use something more sophisticated than LWP::Simple that will hand you back the stream coming in from the server. Parse the incoming stream and drop it when you find the magic line. Or roll your own HTTP request with IO::Socket::INET.
• Parallelization is your friend, but you can't be faster than the slowest engine. Get benchmarks and attack the slow ones first.