Not so complex, and not so memory hungry (+20%):

#! perl -slw
use strict;
use sort qw[_quicksort];
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];

our $N //= 1e6;
our $M //= int $N / 10;

my $val = 'AAAAA';
my %words;
undef $words{ $val++ } for 1 .. $N;

<STDIN>;

my $start = time;
my @ordered;
my @temp; $#temp = $M;
while( my $n = keys %words ) {
    my $m = $n < $M ? $n-1 : $M-1;
    $#temp = $m;
    $temp[ $_ ] = scalar each %words for 0 .. $m;
    delete @words{ @temp };
    push @ordered, @temp;
}

@ordered = sort @ordered;

my $elapsed = time - $start;
printf "Took %.6f seconds for $N items (%.6f per item)\n",
    $elapsed, $elapsed / $N;

<STDIN>;
__END__
C:\test>junk38 -N=10e6 -M=10e3
1.5gb
Took 113.162400 seconds for 10e6 items (0.000011 per item)
1.8gb
[download]