There is no need for any empirical evidence. This is pure mathematics.
Step 1:
Assume a force is conservative. This means that ${\vec \nabla} \times {\vec F} =0$
Step 2:
Then, via Green's theorem, you know that the quantity $\int_{a}^{b}{\vec F}\cdot d{\vec s}$ does not depend on the path you take from a to b. (equivalently, this integral is zero if the path corresponds to a closed loop)
Step 3:
Then, since the value of that integral is independent of the path, you can then say that the value of $\int_{a}^{b}{\vec F}\cdot d{\vec s}$ depends ONLY on the points a and b, and therefore, we can conceptualize a field that takes a values $V(a)$ and $V(b)$ and that satisfies $\Delta V_{a\rightarrow b} = -\int_{a}^{b}{\vec F}\cdot d{\vec s}$
Step 4:
Since (we are assuming $\vec F$ is the only force in the universe here), ${\vec F} = m{\vec a}$, we have (forgive my abuse of differentials moving the dt over, it's faster than the more rigorous result using the chain rule):
$$\begin{align}
\int {\vec F}\cdot d{\vec s} &= m\int {\vec a}\cdot d{\vec s}\\
&= m\int \frac{d{\vec v}}{dt}\cdot d{\vec s}\\
&= m\int d{\vec v} \cdot \frac{d{\vec s}}{dt}\\
&=m\int {\vec v}\cdot d{\vec v}\\
&=\frac{1}{2}mv_{f}^{2} - \frac{1}{2}mv_{i}^{2}
\end{align}$$
Step 5:
Thus, putting steps 3 and 4 together, we find that
$$\Delta V = - \Delta KE$$
or, as is more commonly written
$$\Delta KE + \Delta PE = 0$$
So, there are no real assumptions or empirical observations necessary. All it is is calculus and starting with a force that is conservative (the gravitational force you quote DOES satisfy ${\vec \nabla} \times {\vec F} = 0$, which you can check.). Note that this method lets you derive the potential energy for ANY conservative force without appealing to conservation of energy--you actually PROVE the latter without assuming it!