The list manipulation stuff is fun, but when you stack it too deep it becomes unreadable. The problem is that it has to be read from back to front to get the order right. To fix it, I'd just use more temp variables and more lines. Here's a shot at a rewrite:

our $PADDING = 2; # config, so probably belongs at top of file

my @phrases = ( keys %lists, map { @{$_} } values %lists );
my @lengths = map { length($_) } @phrases;
@lengths      = sort { $b <=> $a } @lengths;
my $longest  = shift @lengths;

return $longest + $PADDING;
[download]

It's a lot longer, but it scans quickly, and if you need to come back and modify one of the steps it will be obvious where to do it.