Searching Installed Apps Marshmallow 6.0.1
Search is working again on my phone. It seems the system rebuilds an index of sorts on its own, I just had to be more patient.

Marking as answer in case someone else has the same experience and hasn't waited a day for the indexing to finish.