P-MOS Selection for 12v application
What characteristics matter most when selecting a part for this
particular job?

Well, you haven't said what the load is and what volt-drop can be tolerated in the PMOS transistor. If I were to assume that \$R_{DS(ON)}\$ was the most important critieria I could make a comparison: -
The DMP1045UQ has around 25 milli ohms on-resistance but the DMP3098LQ is 83 milli ohms on-resistance at a load of 0.5 amps. I just chose 0.5 amps as a guess for what your load might be. So, if that criteria is important, then the DMP3098LQ may not be good enough.
The PMV65XP is about 55 milli ohm on-resistance at 0.5 amps so neither of the alternatives are significantly close to the original (failing) part to be considered.
But, you might not need such a high-spec on-resistance - only you can tell us.

Either one of these should work, correct?

Impossible to say without knowledge of your load and the acceptable volt-drop that can be tolerated in the PMOS transistor when driving it.

The Vgs given my circuit is -12v, right?

Correct on the face of it but, can that 12 volts rise any higher or lower when active - this might make a difference and, also, is it subject to noise or spikes superimposed on the 12 volts - this could make a massive difference to the choice of PMOSFET.
The characteristics of your load could ruin a few little MOSFETs if not taken properly into account. I'm thinking back-emf, inductive load etc..