#use Data::Dumper;
my @array = (
    'Main//Reviews//PS2',
    'Other Menu//Other//Sub//Menus',
    'Main//Reviews//XBox',
    'Main//News',
    'Main//Reviews//PC'
);
array2list(@array);

sub array2list() {
 my %h;
 for (@_) {
 my $hr = \%h;
 for (split('//', $_ )) {
  $hr->{$_} = [(scalar keys %{$hr}), {}] unless (exists($hr->{$_}));
  $hr = $hr->{$_}[1];
  }
 }
 #print Dumper(\%h),hr;
 displaylist (\%h);
}

sub displaylist() {
 print '<ul>';
 my $hr = shift;
 for (sort {$hr->{$a}[0]<=>$hr->{$b}[0]} keys %{$hr}) {
  print '<li>',"$_"; # $hr->{$_}[0]\n";
  displaylist ($hr->{$_}[1]) if (scalar keys %{$hr->{$_}[1]});
 }
 print '</ul>';
}
[download]

Some comments tomake this a little less confusing:

The Data::Dumper bits can be uncommented if you want to know what the heck %h turns out to be. They are clearly not required.

The ordering requirement means that yo can't just ahve a hash of hashrefs. So each hash value is an array ref containing a order created number and a sub hashref. At the twigs the sub hashref is empty.

the subroutine displaylist() is called recursively to print the UL.../UL for a hashref