Warning: this is pretty darn evil, but since it's almost Halloween I'll post it anyway.

my @array = (
    'Main//News',
    'Main//Reviews//PC',
    'Main//Reviews//PS2',
    'Main//Reviews//XBox',
    'Other Menu//Other//Sub//Menus'

);

my %hash;

foreach (@array) {
  s|(\w+\s+\w+)|\'$1\'|g;
  s|\/\/|\}\{|g;

  eval '$hash{' . "$_" . '} = 1';
}

sub build {
  my $hash = shift();
  while (my ($key, $value) = each %$hash) {
    if (ref $value eq 'HASH') {
      $html .= "<li>$key<ul>\n";
      build($value);
      $html .= "<\/ul>\n";
    } else {
      $html .= "<li>$key\n";
    }

  }
}

my $html = "<ul>";
build(\%hash);
$html .= "<\/ul>";

print $html;
[download]

Update: Of course Jeffa beats me to it... harumph.

Update: The ordering requirement can be satisfied using Tie::IxHash for all of the HoH-based methods in this thread.