Why is high voltage more deadly than low voltage? Why is higher voltage said to be more dangerous? Doesn't higher voltage decrease current as P = IV where P is constant, thus making it less deadly?
 A: Your body’s resistance is roughly equal regardless of the voltage across it. (See note at the end.)  Current goes according to Ohm’s law $V=IR$, so more voltage at fixed resistance means more current. More current is generally more dangerous, especially if it’s passing through you.
Your original reasoning incorporates a fallacy that power is constant in this situation.
Note about resistance: To be more precise about the body's resistance, the skin has a much higher resistance than the rest of the body, and the skin's resistance, as noted in comments does vary based both on its condition and the voltage.  There's some detail on that from from NIH.  These variations, however, are less important at higher voltages and beside the main point above, which is that higher voltage still means higher current, especially at voltage levels at that are actually dangerous.  I assume you weren't living in fear of the 9 V battery in your kids' toys.
A: It's the amount of electrical current that is dangerous. That is, only when the application of a high voltage results in a high current.
High voltage usually will be more dangerous than a lower voltage depending on the resistance. This is due to Ohm's law $$I=\frac{V}{R}$$
However, we can see that the the application of even a low voltage can result in a high current if we have a small resistance.

Doesn't higher voltage decrease current as P = IV where P is constant, thus making it less deadly?

This equation shows that the power is proportional to the applied voltage and the current that results from that, and so power $P$ is not constant when $V$ changes.
In most situations, because the human body is of relatively uniform resistance (unless there is water present, or something else that will decrease resistance and allow more current to flow), applying a higher voltage will create a proportionally larger current.
