How does one prove that Energy = Voltage x Charge?

There are various ways to decide which of the assumptions are primary and which of them are their consequences but $E=VQ$ may be most naturally interpreted as the definition of the potential.

The potential energy is a form of energy and the potential (and therefore voltage, when differences are taken) is defined as the potential energy (or potential energy difference) per unit charge, $V = E/Q$. That's equivalent to your equation. The potential energy is proportional to the charge essentially because of the linearity of Maxwell's equations (the superposition principle). Once we know about the proportionality, we must just give a name to the proportionality factor between $E$ and $Q$ and we simply call it potential (or voltage).

There are several (equivalent) ways to look at this.

One is to say that for any conservative force $\mathbf{F}$, one can define the potential energy Ep as an associated potential field such as $\mathbf{F}=-\frac{\partial Ep}{\partial r}$, or maybe more formally $\mathbf{F}=-\nabla(Ep)$. That's no more than a definition of the potential energy. (Electrostatic forces and gravitational forces have that in common that they are conservative and an associated potential function exists).

At the same time electrostatic forces are (experimentally) observed to be $\mathbf{F} = q\mathbf{E}$.

Last definition is the electric potential field U : it is also defined as $\mathbf{E}=-\frac{\partial U}{\partial r}$, or maybe more formally $\mathbf{E}=-\nabla(U)$.

When one puts all these together, Ep = qU.

I am not sure if this is a proof though, but maybe more the consequence of various definitions of useful quantities and concepts in physics.