One thing that really affects performance in this area is how often that the screen is updated. Windows notepad is really poor in this regard in that they update the display after every replace. JEdit which is my default editor does the replace in a buffer then writes that buffer to the screen. By not forcing a refresh after every replace you cut down the time considerably.

It sounds like NoteTab Lite is doing the same as Windows Notepad or do it slightly better by doing it in blocks of lines at a time. Either way not the best method.