[chorny]

Использовать модули CGI (или аналогичные попроще) и MIME::Lite. Тогда программа сильно упрощается. А вообще - надо в заголовках письма проставлять кодировку. И сама программа должна быть в правильной кодировке.