It seems to me that bigger is the string, longer is the time to get its size, (exponentialy?).

Linearly. Perl_utf8_length is basically:

while (start_ptr < end_ptr) {
    start_ptr += UTF8SKIP(start_ptr);
    len++;
}
[download]

and UTF8SKIP just returns the number of bytes in a utf-8 encoded codepoint given the starting byte. So, basically, PL_utf8_length is O(N), where N is the number of codepoins in (SvUTF8) string.

Your LenTestA is exponential because it basically does

PL_utf8_length($chunk)                    # first iteration
PL_utf8_length($chunk . $chunk)           # second iteration
PL_utf8_length($chunk . $chunk . $chunk)  # third iteration
...and so on...
[download]

while LenTestB is

PL_utf8_length($chunk)  # 1st
PL_utf8_length($chunk)  # 2nd
PL_utf8_length($chunk)  # 3rd
...
[download]