I am trying to prove the following:
$$\cos^{-1}x+\cos^{-1}y=\begin{cases}\cos^{-1}(xy-\sqrt{1-x^2}\sqrt{1-y^2});&-1\le x,y\le1\text{ and }x+y\ge0\\2\pi-cos^{-1}(xy-\sqrt{1-x^2}\sqrt{1-y^2});&-1\le x,y\le1\text{ and }x+y\le0\end{cases}$$
Let $\cos^{-1}x=A, \cos^{-1}y=B.$ Since $-1\le x,y\le1\implies0\le A,B\le\pi\implies0\le A+B\le2\pi$
$\cos(A+B)=\cos A\cos B-\sin A\sin B=xy-\sqrt{1-x^2}\sqrt{1-y^2}$ (since the sine function is positive in $1$st and $2$nd quadrants.)
Therefore, $\cos^{-1}(xy-\sqrt{1-x^2}\sqrt{1-y^2})=\cos^{-1}(\cos(A+B))=\begin{cases}A+B;&0\le A+B\le\pi\implies0\le A,B\le\frac\pi2\\2\pi-(A+B);&\pi\le A+B\le2\pi\implies\frac\pi2\le A,B\le\pi\end{cases}$
From this, how do we conclude about $x+y$?
In first case you found that
$$0\leq A+B\leq \pi$$ which becomes
$$0\leq\cos^{-1}x+\cos^{-1}y\leq \pi$$
Note the first inequality above is true for all $x,y\in[-1,1]$
Now the second inequality becomes $$\cos^{-1}x+\cos^{-1}y\leq \pi$$
$$\cos^{-1}x\leq\pi-\cos^{-1}y$$
$$\cos^{-1}x\leq\cos^{-1}(-y)$$
Now $f(x)=\cos^{-1}x$ is strictly decreasing function , therefore $$\cos^{-1}x\leq\cos^{-1}(-y)\implies x\geq-y\implies x+y\geq0$$
because for a decreasing function $$f(x)\leq f(y)\iff x\geq y$$
Similarly second case could be proven.