I have a vested interest in your question as I have a B&W photography background, and frequently convert color images to grayscale (I'm not British... :). Given this, perhaps the following will assist you--at least to start:

use strict;
use warnings;
use File::Find::Rule;
use File::Basename;
use File::Path qw/mkpath/;
use List::Util qw/sum/;
use GD;

my $sourceDir = 'A';
my $destinDir = 'B';

-d $sourceDir  or die 'Error: Source directory does not exist.';
!-d $destinDir or die 'Error: Destination directory already exists.';

my @files = File::Find::Rule->file()->name(qr/\.png$/i)->in($sourceDir
+)
  or die 'No png files found in source directory.';

print "\nNumber of png files to convert to grayscale: ", scalar @files
+, "\n\n";

for my $pngFile (@files) {
    my $destinPath = $pngFile =~ s{^$sourceDir(?=/)}{$destinDir}r;
    my $dir = dirname($destinPath);

    if ( !-d $dir ) {
        mkpath( $dir, { error => \my $err } );
        !@$err or die qq{Unable to create directory "$dir"};
    }

    print "Processing: $pngFile";
    my $image = GD::Image->new($pngFile);

    for my $i ( 0 .. $image->colorsTotal() - 1 ) {
        my @gray = ( ( sum $image->rgb($i) ) / 3 ) x 3;
        $image->colorDeallocate($i);
        $image->colorAllocate(@gray);
    }

    open my $fh, '>', $destinPath or die $!;
    binmode $fh;
    print $fh $image->png;
    close $fh;

    print " - Done!\n";
}

print "\nJob completed.\n";
[download]

Sample output when running:

Number of png files to convert to grayscale: 6

Processing: A/adelaide-rosella.png - Done!
Processing: A/frog.png - Done!
Processing: A/C/chicken_profile.png - Done!
Processing: A/C/tux.png - Done!
Processing: A/C/D/crowned_crane.png - Done!
Processing: A/C/D/cuckoo.png - Done!

Job completed.
[download]

There's likely a more efficient way to do this, but it worked well in my tests--although I'm not processing millions of images. You'll notice that I used GD for the actual image processing. If you're keen on using ImageMagick, you could just modify this script for it.

It will preserve the structure of the source directory, mirroring it in the destination directory, and convert all found png files to grayscale, and then write them into their destination directory. There's an initial check for the destination directory already existing, since files might otherwise be overwritten.

Hope this helps!