Tie::Scalar is included with perl since 5.002. But, unsurprisingly, you can't specify a package as a prereq if it isn't a file whose name is derivable from the package name. TheDamian should have caught this bug in his Makefile.PL.
It appears it's just a bug in the prerequisites list for Regexp::MatchContext, or if you want to look at it that way, in ExtUtils::MakeMaker's checking for available modules. In practise it shouldn't matter as long as you have a "recent" (less than 10 years old) version of perl.