Erg, teach me to start optimising in the most stupdi places. I have modded my code to loop like yours, and moved my hash creation outside the inner loop (what a dummy!) and ditched the sub (which was mostly there for clarity, anyway). Then we get:

    my $out;

    for my $i (0 .. $#lines) {
        my %words1 = map { $_ => 1 } split /_/, $lines[$i];
        for my $j($i + 1 .. $#lines) {
            if (1 < grep $words1{$_}, split /_/, $lines[$j]) {
                $out .= "$lines[$i] and $lines[$j]\n";
            }
        }
    }
    $out;
[download]

Faster! Benchmark:

Benchmark: running bmann, jasper, rev for at least 3 CPU seconds...
     bmann:  3 wallclock secs ( 3.17 usr +  0.00 sys =  3.17 CPU) @ 88
+28.71/s (n=27987)
    jasper:  3 wallclock secs ( 3.15 usr +  0.00 sys =  3.15 CPU) @ 10
+860.32/s (n=34210)
       rev:  3 wallclock secs ( 3.17 usr +  0.00 sys =  3.17 CPU) @ 22
+06.94/s (n=6996)
[download]