Your child process management logic is flawed.

Try this (slightly improved, but simplistic) code:

use strict;
use warnings;
#Hash of Child PIDs
our %ChildPids;

#my $MaxThreadsAtOneTime = 5;
my $MaxThreadsAtOneTime = 2;
#my $MaxThreadsAtOneTime = 1;
my $ThreadsToRun = 10;

#### MAIN

# Submit first group of children
print("Submitting first batch of children\n");
my $ThreadNum = 0;
my $activeThreads = 0;
while ($ThreadNum < $ThreadsToRun) {
    $ThreadNum++;
    my $ChildPid;
    if ($activeThreads >= $MaxThreadsAtOneTime){
        print "Waiting for a thread to finish\n";
        for (keys %ChildPids){
             my $rslt = waitpid( $_,0 );
             print "Waiting pid $_ = ",    $rslt , "\n";
             delete $ChildPids{$_}; # So we dont wait again..
             last;
        }
        $activeThreads --;
    }
    if ($ChildPid = fork) {    
        # parent code
        # Collect pid
        print("Parent Created Child $ThreadNum with pid $ChildPid\n");
        $ChildPids{$ChildPid} = $ThreadNum;
        $activeThreads++;
    } elsif (defined $ChildPid) {
        # child code
        print("     Child pid $$ checking in as thread $ThreadNum\n");
        my $SleepTime = int(rand(10));
        print("     Child pid $$ sleeping for $SleepTime seconds\n");
        sleep $SleepTime;
          print("     Child pid $$ exiting\n");
        exit();
    }
}
print "Parent Code done after ThreadNum=$ThreadNum .. Waiting\n";
for (keys %ChildPids){
   print "Waiting pid $_ = ",    waitpid( $_,0 ) , "\n";
}

print "Exiting Parent\n";
[download]