Reproduced, in Chromium58/Ubuntu and Firefox53/Ubuntu.
The issue seems to be based on the number of rows
I made a test page, with 4 tables, here
https://www.mediawiki.org/w/index.php?title=User:Quiddity_(WMF)/sandbox2&oldid=2480122
Adding a new column to the 34x10 row table is instant.
Adding a new column to the 34x15 row table takes ~5 seconds.
Adding a new column to the 34x20 row table takes ~60 seconds.
Adding a new column to the 10x20 row table takes ~30 seconds.

Definitely related to row count, seems exponential. Debugging shows that each execution of the transactions.forEach() loop at the end of insertRowOrCol takes at least twice as long as the last one.

This makes it completely impossible to insert a column in a table with 36 rows, which is usually one of the killer features of VE!

Slowness traced to ve.dm.Surface.prototye.change, line 873 in debug=true version.
this.emit( 'select', this.selection.clone() );

Looks like select events getting bound and not unbound. this.bindings[select].length is twice as big each time through the trasnactions.forEach() loop, so the loop inside of oo.EventEmitter.emit takes twice as long each time.