Here's an approach that doesn't depend on  /e evaluation or on separate upper-casing (Update: and handles strings with mixed camelCase and non-camelCase words). Note this handles the degenerate camelCase 'aB' correctly, except I'm not sure just what is 'correct' camelCase in this case. No attempt made at benchmarking. Tested under 5.8.9 and 5.12.3.

>perl -wMstrict -le
"unshift @ARGV,
   'not foo camelCase NOT BAR namesCanBeDifferent oK Not Baz';
 ;;
 for (@ARGV) {
   print qq{'$_'};
   s{ ([[:lower:]]*) ((?<=[[:lower:]]) [[:upper:]][[:lower:]]*) }
    {\U$1_$2}xmsg;
   print qq{'$_' \n};
   }
"
"aB aB aB"  " aB "  "aBc aBc aBc"  " aBc "
"No No No"  " No "  "Not Not Not"  " Not "
'not foo camelCase NOT BAR namesCanBeDifferent oK Not Baz'
'not foo CAMEL_CASE NOT BAR NAMES_CAN_BE_DIFFERENT O_K Not Baz'

'aB aB aB'
'A_B A_B A_B'

' aB '
' A_B '

'aBc aBc aBc'
'A_BC A_BC A_BC'

' aBc '
' A_BC '

'No No No'
'No No No'

' No '
' No '

'Not Not Not'
'Not Not Not'

' Not '
' Not '
[download]