A deque is typically the right data structure when you need to append, pop, and extend on both the left and right side.  It is designed specifically for that task.  Also, it nicely cleans-up the code by removing the backwards line list and the list reversal prior to insertion on the left (that's what we had to do to achieve decent performance before the introduction of deques in Python 2.4, now you hardly ever see code like "self._lines[:0] = lines[::-1]").  I think fix_prepending2 would be a nice improvement for Py3.5.

For the main patches that directly address the OP's performance issue, feel free to apply either my or yours.  They both work.  Either way, please add test_parser.diff since the original test didn't cover all the cases and because it didn't make clear the relationship between push() and splitlines().