Huge part of current cost is that the first getNextRange() call on a range iterator sucks: (see the comment on first iteration)
http://docs.ckeditor.com/source/rangelist.html#CKEDITOR-dom-rangeListIterator-method-getNextRange
We pass the range iterator an array of ranges indicating the bad words in the current block. This means that in cases where the block has 1 typo are as slow to mark as blocks that have 99 typos.
some numbers:
in a typical actual-paragraph, the first getNextRange() takes 18ms due to the setup step. Subsequent calls to getNextRange() for additional words are 0.13ms or so.
This also explains why tables can be so stupid:
Suppose you have a table of 1 acronym for cell, each cell will create a new iterator (because each cell is a paragraph.) This is stupid.