The smallest fix is to simply move the 'my' to be inside the loop:

for my $i (1..$depth-1) {
    my $val = 1 + 2*$i;
    push @$loop, sub {[$_+1..$val]};
}
[download]

or, even

my $val= 3;
for my $i (  1 .. $depth-1  ) {
    my $end= $val;
    push @$loop, sub {[$_+1..$end]};
    $val += 2;
}
[download]

and the reason this makes a difference is that your code uses a single instance of the $val variable and all of the closures you make share it. When the closures finally get run [several times each, during the call to NestedLoops()] is when the value of $val is used. $val doesn't stay 3 so your loops don't stop at 3.

You can build the list in-line, for example:

#!/usr/bin/perl -w
use strict;

use Algorithm::Loops 'NestedLoops';

my $depth= 4;
my $iter= NestedLoops(
    [   [0..1],
        map {
            my $end= 2*$_+1;
            sub { [$_+1..$end] }
        } 1..$depth-1,
    ],
);
while(  my @list= $iter->()  ) {
    output(@list);
}

sub output {
    print join '', @_, "\n";
}
[download]