I believe that the problem is not quite as it seems.
The messages should still be "all there". However, with 3.6, messaging was apparently changed so only (confirmed) contacts can send you a message. That is, you only see messages from people in your "contacts" (that you asked to confirm you as a contact, or vice versa). This is essentially meant as a privacy improvement - but it also "hides" your old messages.
For example, I do not see any messages from my student "X" in Moodle 3.6 now. I then searched for "X", clicked on his name, and now I can see all old messages. However, I will have to wait for X to confirm the contact to be able to directly access the (old) messages we exchanged before the upgrade; I can only see them by "searching for X and clicking on X's name". Try this out and it should work for you - as long as you recall who sent you a message.
Alas, I am not able to recall the names of everybody who wrote me a message over the past few days (too many, as I am also the site admin).
I also consider this to be somewhere between "bug" (the messages are seemingly "gone", but not actually "deleted") and "feature" (privacy improvement). I wish there were some way for me to access the list of persons who I exchanged messages with before, e.g., Moodle asking me after the upgrade if I wanted to add them as a contact...
PS. I now added a bug report (https://tracker.moodle.org/browse/MDL-64317) for this, as this makes it more likely Moodle HQ will see and address this issue.