You've probably done it already, but it suddenly struck me that this fixed the right-padding problem without needing to mess with the code much.

sub columnise {
    my( $width, @list ) = @_;
    my @lines;
    for my $rows ( 1 .. @list ) {
        my $cols = int( (@list + $rows -1) / $rows );
        my @aoa = map{
            [ @list[ $_ .. $_+$rows-1 ] ]
        } map{ $_ * $rows } 0 .. $cols-1;
        my @widths = map{
            max map length( $_||'' ), @$_
        } @aoa;
        next if sum( @widths, $#widths * 2 ) > $WIDTH;
        for my $row ( 0 .. $rows-1 ) {
            push @lines, join '  ', map{
                sprintf "%-$widths[ $_ ]s", $aoa[ $_ ][ $row ]||''
            } 0 .. $#aoa;
        }
        return @lines;
    }
}
[download]

I also played with your binary chop idea, but the list had to be quite long and the width quite narrow before it offset the extra code required.