I tried LANG=C and sorting individually (two sorts).

Results from a Linux box:

54 seconds LANG=en_US.UTF-8
33 seconds LANG=C sort -k2,2rn -k1,1
23 seconds LANG=C sort -k1,1 | sort -k2,2rn
[download]

Testing:

#!/bin/sh
# https://www.perlmonks.org/?node_id=11148773

if [ $# -eq 0 ]; then
    printf "Give a list of files to sort.\n" >&2
    exit 1
fi

LANG=C

awk '
   { cat_count[ $1 ] += $2 }
   END {
       for ( cat in cat_count )
           printf "%s\t%s\n", cat, cat_count[ cat ]
   }
' $@ \
| sort -k1,1 | sort -k2,2rn

printf "total time: %d s\n" $SECONDS >&2
[download]