I have cracked this. The clue is here. Although it is referring to something slightly different, the principal is the same: because the child created in the fork inherits the STDIN and STDOUT connected to the web browser, the web browser connection is held open. The parent is exiting properly, and the child is taking over its role, making it seem to the user like nothing has changed. To solve this, you can reopen STDIN and STDOUT to another destination (in my case /dev/null). Obviously you will need to be sure that you are done outputting things to the web browser. The code above is now:

#!/usr/bin/perl -wT

use strict;
use CGI ':standard';

die "Could not fork()\n" unless defined (my $kidpid = fork);
if ($kidpid) {
    print header;
    print "done\n";
    print STDERR "Parent exited\n";
    exit;

}
else
{
    open STDOUT, '>/dev/null' or die "Can't open /dev/null: $!";
    open STDIN, '</dev/null' or die "Can't open /dev/null: $!";
    sleep 20;
    print STDERR "Child exited \n";
}
[download]

which works as you'd want it to. In conjunction with some AJAX you finally get the task maangement you want.

If you want to have a go at storing and restoring STDOUT for later, you can try some examples here.