I'm not sure whether this would work as I haven't thought how to get the remaining "sets" back after culling but here goes. How about using the garbage collection built into Perl by turning your @bools into %bools keyed by the range 1 .. $N and the values being anonymous arrays containing references to any "sets" that contain the number in the key. By delete'ing any key in %bools that is in @someOrder you are left with only references to "sets" that have at least one number reamaining. The "sets" are array references that are now out of scope so once all references are gone they are garbage collected without the need to do a splice. You should then be able to recover the remaining "sets" by combing through %bools for unique array refs.

This idea may be cock-eyed because I don't have time to fully test it now but your code took about 25 seconds on my elderly laptop whereas this code

use strict;
use warnings;

use List::Util   qw{ shuffle };
use Time::HiRes  qw{ time };

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

my %bools = map { $_ => [] } 1 .. $N;

for my $set ( 1 .. $S )
{
    my $conts = [];
    push @{ $conts }, int rand $N for 0 .. int rand $Z;
    push @{ $bools{ $_ } }, $conts for @{ $conts };
}

my @someOrder = shuffle 1 .. $N;
my $start     = time();

delete @bools{ @someOrder };

printf "Took %.6f\n", time() - $start;
[download]

takes about 15ms, although more time would be taken recovering the sets.

I hope I'm not just having a rush of blood and that this is actually helpful.