Just use any of the many algorithms to split an array into smaller chunks. The simplest is to splice until an array is empty:

use strict;
use Fatal qw(chdir opendir mkdir rename);

chdir "...";
opendir my $dh, ".";

my @files = grep !/\A\.\.?\z/, readdir $dh;
my $index = 0;

while (@files) {
    my $dir = sprintf "images%02d", $index++;
    mkdir $dir;
    rename $_, $dir for splice @files, 0, 1000;
}
[download]

You can use the core opendir and readdir functions. I think you should read file by file (due the number of files) and move them using File::Copy.

use File::Copy;
use File::Spec;

my $filecount = 0;
my $dircount = 0;

opendir my $basedir, "." or die $!;
while (my $file = readdir($basedir)) {
    next if $file =~ /^\.\.?$/ or -d $file;
    my $targetdir = "dir${dircount}";
    do { mkdir $targetdir or die $!; } unless -d $targetdir;
    move($file, File::Spec->catfile($targetdir, $file)) or do { warn $
+!; next; };
    if ($filecount > 999) {
        $filecount = 0;
        $dircount++;
    }
}
closedir $basedir or die $!;
[download]

#! /usr/bin/env perl
use strict; use warnings;
die "usage: $0 <dir>" unless @ARGV == 1;

chdir $ARGV[0] or die "chdir failed: $!";
my @files = grep { not /^(?:\.|\.\.)$/ } readdir '.';
my $i = 0;
for (my $i = 0; @files; $i++) {
  mkdir $i or die "mkdir $i failed: $!";
  for (splice @files, 0, 1000) {
    rename $_, "$i/$_" or die "rename $_ $i/$_ failed: $!";
  }
}
[download]

Adjust for win32 as needed.

For fun, perl6:

#! /usr/bin/env perl
use v6;
use fatal; # or is this default?
die "usage: $*PROGRAM_NAME <dir>" unless @*ARGS == 1;

chdir @*ARGS[0];
my @files = grep { $_ ne '.'&'..' } readdir '.';
loop (my $i = 0; @files; $i++) {
  mkdir $i;
  rename $_, "$i/$_ for splice @files, 0, 1000;
}
[download]