I happened to have almost exactly the same issue today. Here's how I handled it:

#! perl

use strict;

my ($file) = @ARGV;
my $counter;
my $file_name = 1;
open OUT_FILE, "+>$file_name.xls";
open IN_FILE, "<$file";
while (<IN_FILE>){
    $counter++;
    print OUT_FILE $_;
    if($counter%20000 == 0){
        $file_name++;
        open OUT_FILE, "+>$file_name.xls";
            }
    }
[download]

update: I happened to want to split my file into 20,000-line files, obviously. I got 22 of them.