I managed to get it to do what i wanted. The answer is:
Edit “admin-functions.php”. In line 84, add:
$result[$cat]['cat_description'] = category_description($cat);
In line 91, change the echo-line of the write-nested-categories functions to the following:
echo '<label for="category-', $category['cat_ID'], '" title="', $category['cat_description'], '" class="selectit"><input value="', $category['cat_ID'],
that’s it.
And it shows me how many SQL queries wordpress is uttering to get some output — which explains why it does not scale that well…