> Not necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like.

Have a look at the proof of the Robertson-Seymour theorem. Here the Wikipedia section about its importance in complexity theory:

> https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...