A kind-of recursive sort that doesn't require decoration.

use strict;
use warnings;

use Data::Dumper;

my @AoA = (
   ['blah', 'asdf', 'foo', 'bar'],
   ['two'],
   ['zzz', 'def', 'ghi'],
   ['one'],
   ['mmm', 'def', 'ghi'],
   ['qqq', 'xyz', 'aaa'],
   );

my @sortedAoA = do {
   my $recSort;
   $recSort = sub {
       my @arrA = @{ $_[ 0 ] };
       my @arrB = @{ $_[ 1 ] };

       return 0 unless @arrA;
       return ( pop( @arrA ) cmp pop( @arrB ) )
          || $recSort->( \ @arrA, \ @arrB );
       };

   sort { @$a <=> @$b || $recSort->( $a, $b ) } @AoA;
   };

print Data::Dumper->Dumpxs( [ \ @sortedAoA ], [ qw{ *sortedAoA } ] );
[download]

The output.

@sortedAoA = (
               [
                 'one'
               ],
               [
                 'two'
               ],
               [
                 'qqq',
                 'xyz',
                 'aaa'
               ],
               [
                 'mmm',
                 'def',
                 'ghi'
               ],
               [
                 'zzz',
                 'def',
                 'ghi'
               ],
               [
                 'blah',
                 'asdf',
                 'foo',
                 'bar'
               ]
             );
[download]

I hope this is of interest.

Update: Renamed the @revA and @revB variables to @arrA and @arrB as the final solution used pop rather than reverse and shift but I'd forgotten to rename at the time.