$('ul.menu').each(function(){ 
	var li = $('li',this), length = Math.ceil(li.length / 4), i = 0, uls = $('<div></div>');

	for(; i < length; i++){
		$('<ul class="menu"></ul>').append(li.filter(':gt(' + (i*4-1) + ')').filter(':lt(' + (i+1)*4 + ')')).appendTo(uls); 
	}
	$(this).replaceWith(uls.children());
});

Или элегантней, но не оптимально:

$('ul.menu').each(function(){ 
	var i = Math.ceil($('li',this).length / 4), uls = $('<div></div>');

	while(i--) $('<ul class="menu"></ul>').append($('li',this).filter(':lt(4)')).appendTo(uls); 
	$(this).replaceWith(uls.children());
});

Спасибо! Сравнив со своими потугами, понял, что пытался делать проще, но не получил бы рабочего кода.