Pseudo-code (unchecked, just thrown out there, etc - Time::Progress). Sorry it's not more complete.

use Time::Progress;

my ( $total ) = /?/ =~ qx/ du -something -or -other target_dir /

my $prog = Time::Progress->new();

$prog->attr( min => 1, max => $total );

while ( file_finding() ) {
   $size += $size_of_current_file
   print $prog->report( "%70b %p\r", $size );
}

$prog->stop;
# report times
print $prog->elapsed_str;
print $p->estimate_str;
[download]