This drops into Inline::C to explore the bitmap and construct the hash. It takes 23 seconds to process a 125 megapixel image:

#! perl -slw
use strict;
use Inline C => Config => BUILD_NOISY => 1;
use Inline C => <<'END_C',  NAME => '_1138218', CLEAN_AFTER_BUILD =>0;
typedef unsigned __int64 U64;
typedef unsigned   int   U32;
typedef unsigned   char  U8;

HV* countColors( SV *img ) {
    STRLEN l;
    U32 *rgba = (U32*)SvPVx( img, l ), i;
    HV* counts = newHV();

    l /= 4;
    for( i = 0; i < l; ++i ) {
        if( hv_exists( counts, (char*)&rgba[ i ], 4 ) ) {
            SV **val = hv_fetch( counts, (char*)&rgba[ i ], 4, 0 );
            SvIV_set( *val, SvIV( *val ) + 1 );
        }
        else {
            SV *val = newSViv( 1 );
            hv_store( counts, (char*)&rgba[ i ], 4, val, 0 );
        }
    }
    return counts;
}


END_C
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];
use List::Util qw[ sum ];
use GD;

GD::Image->trueColor(1);

my $i = GD::Image->new( $ARGV[ 0 ] ) or die $!;

my $gd = $i->gd;
my( undef, $width, $height, undef, undef ) = unpack 'nnnCV', substr( $
+gd, 0, 11, '' );
printf "Width:%u height:%u pixels:%u\n", $width, $height, length( $gd 
+) / 4;

my $start = time;
my $href = countColors( $gd );
printf "Took %f seconds\n", time() -$start;

printf "Found %u colors in %u pixels\n", scalar( keys %{ $href } ), su
+m( values %{ $href } );

__END__
C:\test>1138218 mid.png
Width:12800 height:10240 pixels:131072000
Took 23.391081 seconds
Found 81814 colors in 131072000 pixels
[download]

The handling of the hash could be made more efficient by only calculating the hash-values once instead of several times; and by pre-extending the hash.