I have never aimed Perl at an embedded environment. However this guy has a small Perl 5.6 whose RPM takes 629756 bytes. I don't know if the perl in there is signifcantly larger uncompressed.

I have heard that for a variety of reasons (some of which will be addressed in Perl 6) Perl 5 is a poor candidate for embedding. If you want the ability to go with a high-level language in an embedded environment but don't want to lose OO support, a better bet would be Ruby or Python. For instance the Palm port of Python fits an interpreter in 173 K.