Not strictly a perl solution, but you could use ajax to handle this. Your CGI would return a page that says processing and exit. This page would have some javascript that would periodically do an xmlhttprequest to a status script on the server. When the job is done the javascript would get the finished status from the status script and update the page accordingly.
Info on ajax and perl http://www.modernmethod.com/sajax/