I don't see any obvious memory leaks, unless you are calling this method more than once. Each time through you create a new QTextDocument instance; if you aren't getting rid of these and are calling this method over and over, then you'll keep accumulating dangling pointers to the old documents and using up more and more memory.
This really does scream to be represented as a table. You're formatting it that way, so just use a QTableWidget or QTableView and turn off the grid lines.
The amount of time could be because the document is recomputing its internal layout with each line you add to it and possibly pushing everything onto undo / redo stacks with each addition. The default value for the undoRedoEnabled property is true, and I don't see where you disable it. So you might have an undo stack with 500K blocks on it.
Bookmarks