Reverse your data structures:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use List::Util qw[ shuffle ];
use Time::HiRes qw[ time ];

our $N //= 1e3;
our $S //= 1e4;
our $Z //= 5;

my @bools = (0) x $N;

my @sets = map [
    map int( rand $N ), 1 .. 1 + int( rand $Z )
],1 .. $S;

my @sets1 = map [@$_], @sets;

my @someOrder = (shuffle 0 .. $N-1);

my $start = time;
for my $next ( @someOrder ) {
    $bools[ $next ] = 1;
    for my $set ( reverse 0 .. $#sets ) {
        if( grep( $bools[ $_ ], @{ $sets[ $set ] } ) == @{ $sets[ $set
+ ] } ) {
            splice @sets, $set, 1;
        }
    }
}
printf "Took %.6f\n", time() - $start;


$start = time;

my @sizes = map scalar(@$_), @sets1;
my @revsets = map [], @bools;
my %sets;

for my $set_ix (0..$#sets1) {
    if (@{$sets1[$set_ix]}) {
    $sets{$set_ix} = $sets1[$set_ix];
        for my $bool (@{$sets1[$set_ix]}) {
            push @{$revsets[$bool]}, $set_ix;
        }
    }
}

for my $next ( @someOrder ) {
    for my $set_ix (@{$revsets[$next]}) {
        unless (--$sizes[$set_ix]) {
            delete $sets{$set_ix};
        }
    }
}
printf "Took %.6f\n", time() - $start;
[download]

and it runs as...

Took 10.198676
Took 0.112004
[download]