Just for kicks, and with extended character classes (5.005 or later? Not sure.):

my $str = "AbcDefGhiJkl";
$str = join "::", split(/(?<=[[:lower:]])(?=[[:upper:]])/, $str);
print "$str\n";
[download]

Update: Ok, it is slower, but interesting nonetheless and still maybe worthwhile to use the [:lower:] and [:upper:] character classes even on blakem's answer.