Now hold on for a second:

Warn? Yes a warning would have been nice. Not handled correctly? No.

Documentation of Storage promises that Storage will work for SCALAR, ARRAY, HASH or REF objects:

There is no promise that Storage will handle lvalue's and it doesn't, so one may actually reason it is functioning correctly.

The example script below first shows the effect of storing the lvalue in an array and changing it to undef outside of the array. After that it shows that the same behavior cannot be observed after using the Storage. The lvalue is invalidated and becomes undef. Same behavior can be observed when the lvalue is inside a hash, also the correct behavior if you ask me. I do believe a warning would have been nice though:

use strict ;
use warnings ;
use Storable qw( freeze thaw ) ;
use Data::Dumper ;

my $abc = "abc" ;
my @ar = ( \( substr( $abc, 0 ) ) ) ;
print "ar_0 = ${$ar[0]}\n" ;

my $def = "def" ;
my @ar2 = ( \( substr( $def, 0 ) ) ) ;
$def = undef ;
print "ar2_0 = ${$ar2[0]}\n" ;

$def = 'def' ;
print "ar2_0 = ${$ar2[0]}\n" ;

my $serialized1 = freeze \$abc ;
my $serialized2 = freeze \substr $def, 0 ;
$abc = 'ghi' ;
$def = 'jkl' ;
$abc = ${ thaw( $serialized1 ) } ;
$def = ${ thaw( $serialized2 ) } ;
print "thaw abc = $abc\n" ;
print "thaw def = $def\n" ;

my $xyz = "xyz" ;
my %xyz = ( _xyz => \substr $xyz, 0 ) ;
my $ser_xyz = freeze \%xyz ;
$xyz = "uvw" ;
my %copyxyz = %{ thaw( $ser_xyz ) } ;
print Dumper( \%copyxyz ) ;

__END__
ar_0 = abc
Use of uninitialized value in concatenation (.) or string at test2.pl 
+line 13.
ar2_0 =
ar2_0 = def
thaw abc = abc
Use of uninitialized value $def in concatenation (.) or string at test
+2.pl line 25.
thaw def =
$VAR1 = {
          '_xyz' => \undef
        };
[download]

Thank you everyone for valuable answers. Eily, maybe you'll find this funny, too:

use strict;
use warnings;
use feature 'say';
use Devel::Peek;
use Storable qw/ freeze thaw /;

my $s = 'abc';
my $r = \substr $s, 1, 1;

say ref $r;                 # LVALUE
Dump $r;                    #
say ${ thaw freeze $r };    # failure

$$r = 'Z';

say ref $r;                 # LVALUE again
Dump $r;                    # ref target is now POK, PV is "Z"
say ${ thaw freeze $r };    # "Z"
[download]

After first direct use for the purpose it was designed for in general and created in this very test, the substr's LVALUE magic is still there, and yet referent's POK flag is set, and Storable is fooled to DWIM.

The return value LVALUE indicates a reference to an lvalue that is not a variable. You get this from taking the reference of function calls like pos or substr.

Why, here you are:

use strict;
use warnings;
use feature 'say', 'state';
use Devel::Peek;
use Storable qw/ freeze thaw /;

sub foo : lvalue { state $r; $$r }
foo = 42;

say ref \foo;               # SCALAR
Dump \foo;                  # Nothing interesting. Much 
                            # shorter output than one 
                            # full of magic, above.
say ${ thaw freeze \foo };  # 42
[download]

Wait, but it was exactly "reference to an lvalue that is not a variable"! Hm-m, though, they didn't say the reverse is true... So the LVALUE that confuses Storable, is limited to references to substr and pos (?).

----

Storable, indeed, promises only to work with "SCALAR, ARRAY, HASH or REF objects". But it successfully deep-clones references to e.g. variables long out of scope. From there, maybe it's not too long distance to clone a string to which \substr refers.

As much as the above would be interesting (if it worked), I only wanted, in OP, to pass values, not LVALUE magic. For that, Sereal DWIMs. Storable doesn't.

But I really should have done as in first line:

@result = mce_map { ...work with $_ } substr(...)
@result = mce_map { ...work with $$_ } \substr(...)
@result = mce_map { ...work with $$_ } \( my $s = substr(...))
[download]

(2nd parameter is "array of", of course) and not in any of 2 next lines. 2nd only works with Sereal. Depending on strings length and number, benchmark shows either of the 3 can be up to 30% faster than others, with mce_map block being no-op. Which is irrelevant, this gain is tiny compared to time required for real job. Consumed memory was also almost the same for all 3, as duplicates were created anyway (by Sereal?) in 2nd case.

----

BrowserUk, the route you suggest makes perfect sense, if parallelism was fine-tuned by hand, especially since ultimate source of all strings (from which substrings were further extracted) is single large file with kind of TOC (long story...). But mce_map is so amazingly convenient to transparently add parallelism here, all long time consuming work happens per substring inside its block.