If you aren't using utf8 for your Cyrillic data, what encoding are you using? (ISO8859-5? CP1251? KOI8?) Whatever it is, Perl 5.8 has a means built in to convert it into utf8. Once the text is in utf8 (or if you're using utf8 already), then it's really simple:
$_ = lc();
The conversion to utf8 (and back to whatever you started with) is also simple, using either a PerlIO layer or the Encode module -- e.g., if your input data is cp1251, you can open an input file like this:
open( IN, "<:encoding(cp1251)", $filename ) or die $!;
This way, the text you read in is automatically converted to perl's internal utf8 encoding, and all character-based operators and functions (lc, uc, length, substr, regexes, cmp, eq, and so on) will work the way you want them to, regardless of what language the text is in. Look through the Encode, PerlIO, perluniintro and perlunicode man pages for more details.