It's not so much being succinct, although clean code often is. The key bits are:

• Handle the initial empty list case outside the loop to make the loop cleaner.
• Use Perl's "last element index" (-1) so you don't need to count stuff.
• Handle "time for a new segment" and "add a value" as independent operations.
• Work with the index of the next interesting value, not the value.
• Clean up as you go.

although upon reflection I'd change @lists = grep{scalar @$_} @lists; to splice @lists, $smallest, 1 if !@{$lists[$smallest]};.