How to implement Brown Clustering Algorithm in O(|V|k^2)
I have managed to resolve this. There is an excellent and thorough explanation of the optimization steps in the following thesis: Semi-Supervised Learning for Natural Language by Percy Liang.

My mistake was trying to update the quality for all potential clusters pairs. Instead, you should initialize a table with the quality changes of doing each merge. Use this table to find the best merge, and the update the relevant terms that make up the table entries.