Text::Wrap isn't necessarily overkill. What about words that are longer than 12 characters? The answers given so far don't handle that, so far as I can tell. Text::Wrap isn't the greatest, but at least doesn't lose any letters.

This code is also a bit more readable, in my opinion.

use warnings;
use strict;

use Text::Wrap qw(wrap);

my $phrase = 'This is a test message with lots of words in it. Tintina
+bulations!';

$Text::Wrap::columns = 13;
my $wrapped = wrap('','',$phrase);

print $wrapped;
[download]