Why do increasing regularization weights make objective function not monotonically decrease?

Forgive me for not being an expert on NMF, but I am pretty experienced with other regularized techniques.

Regularization techniques usually use a form of gradient descent to find the optimal answer. In general, these are guaranteed to converge. However, they are not often guaranteed to do so monotonically.

The geometric interpretation of gradient descent is searching for the bottom of a bowl by walking down the sides of the bowl. Think about an image like this. The size of those steps depends on the algorithm used. It's usually computationally cheap to have a constant or monotonically decreasing step size. If the step size is too large, which is likely in the beginning of your algorithm, then you can "overshoot" your goal, and hence end up with an iteration larger than the previous one.