I solved this in a kind of hacky way by searching with a from:username query in the Discord app, looking at the http request with Chrome DevTools, and finally recreating the request with the python module requests.
In Discord, you can open DevTools with ctrl+shift+i on Windows or Linux, command+option+i on Mac.
In DevTools, navigate to the Network tab.
I'd suggest to fill in the search query (but don't hit enter), then open devtools, then hit enter on the search. Otherwise there will be a lot of http requests that pop up as you type.
Then, you find the request with a name that looks like "search?author_id=1234567890". If you click on that request, you can see the details necessary to recreate it.
The key parts of the http request you need to use are the Request Headers section and the Request URL under the General section, all in the Headers tab that pops up when you first click on the request, and the Response tab to see what your response will look like.

The accept-encoding attribute of the Request Headers includes br, but this seems to jumble the result. Keeping it to just gzip, deflate works for me.
Using the requests python module this should be pretty easy to set up. So long as br is not listed in accepted-encoding, you should be able to use the json() method of requests, and for the particular problem of finding the total messages sent by the user (whose id you must insert into the request URL), it's simply accessible with my_request_variable.json()['total_results'].
The main thing to watch out for is the authorization request header. This is unique to the user (you, unless you do all this from someone else's account) and you can't substitute in a discord bot's token, unfortunately.