The best way that I could think to accomplish something like this would be to sort through the first folder and create a hash with the date (or whichever property of the message you wish to sort by) and message id. Then sort the hash and pull each message by id and put it into a new "sorted" folder. I used the CPAN module Mail::Box::Manager.

For example:

 use Mail::Box::Manager;

 my $unsorted_folder = "inbox";
 my $sorted_folder = "inbox.sort";
 my %msghash;
 my $mgr    = Mail::Box::Manager->new;
 my $unsortfolder = $mgr->open(folder => $unsorted_folder);
 my $sortfolder = $mgr->open(folder => $sorted_folder);

 # iterate over the messages & create the hash
 foreach my $id ($unsortfolder->messages) {
   my $message = $unsortfolder->message($id);
   $msghash{$id} = $message->get('Date');
 }

 # compare the dates & add to new folder
 foreach my $msg (keys %msghash) {
   @datesorted = <date sorting algorithm>
   foreach (@datesorted) {
     $sortedfolder->addMessage($unsortedfolder->message($_));
   }
 }
$unsortfolder->close();
$sortedfolder->close();
[download]

The code is untested. I'm sure there is probably a better way to do this. To sort by dates, look into using the CPAN module Date::Manip. Hope the concept helps.