After reading through the documentation some more, I found the Open method:

$subKey= $key->Open( $sSubKey, $rhOptions )

    The Open method opens a Registry key and returns a new Win32::TieR
+egistry
object associated with that Registry key. If Open is called via a refe
+rence to
a tied hash, then Open returns another reference to a tied hash. Other
+wise Open
returns a simple object and you should then use TiedRef to get a refer
+ence to a
tied hash.

    $sSubKey is a string specifying a subkey to be opened. Alternately
+ $sSubKey
can be a reference to an array value containing the list of increasing
+ly deep
subkeys specifying the path to the subkey to be opened.

   ...
[download]

Which seems to do the trick in my modified program:

#!/usr/bin/perl -w
#
#  Attempt to delete 'HKEY_CLASSES_ROOT/Folder/shell/xyzzy_1' from the
#  Windows Registry, using Win32::TieRegistry.
#
#  This version uses the 'Open' method -- Success!
##


#############
# Libraries #
#############
use strict;
use warnings;
use Data::Dumper;
use Win32::TieRegistry( Delimiter => '/' );


################
# Main Program #
################

# Step 1 -- assign to the 'Folder' key
my $label    = "xyzzy_1";
my $key      = 'HKEY_CLASSES_ROOT/Folder';
my $h_folder = $Registry->{$key};
(defined $h_folder) or die "Unable to find registry key '$key'\n";

# Step 2 -- open at the 'shell' subkey
my $h_shell  = $h_folder->Open('shell', { 'Delimiter' => '/' });
$h_shell or die "Unable to open subkey 'shell' (of key '$key')\n";

# Step 3 -- Display values for the 'shell' subkey
print "[Values for '$key/shell']\n";
my $idx = 0;
foreach my $key (keys %$h_shell) {
    printf "  %3d.  %s\n", ++$idx, $key;
}
print "\n\n";

# Step 4 -- Validate that the label 'xyzzy_1' was found
if (!exists($h_shell->{"$label/"})) {
    die "No such label for '$key' => '$label'\n";
}

# Step 5 -- Delete 'xyzzy_1' from the 'shell' subkey
print "Deleting label '$label' ...\n";
my $result = delete($h_shell->{"$label/"});
printf "Result of delete:  '%s'\n", Dumper($result);
[download]

One caveat is that, if the regedit program is open, you must refresh its state after the delete (View > Refresh or function key F5), otherwise the display will continue to show the deleted key (eg. 'xyzzy_1'), but clicking on it (and other operations) will give a regedit error.