Solution which worked for me:
It was possible to avoid merged regions, so I could iterate through the other cells and finally autosize to the largest cell like this:
int width = ((int)(maxNumCharacters * 1.14388)) * 256;
sheet.setColumnWidth(i, width);
where 1.14388 is a max character width of the “Serif” font and 256 font units.
Performance of autosizing improved from 10 minutes to 6 seconds.