- $U(x,y) = \sqrt{x^2 - y^2}$ indeed has concave indifference curves. As you pointed out, this can be found by setting utility to a constant level $\overline{U}$.
$\overline{U} = \sqrt{x^2 - y^2} \iff \overline{U}^{2} = x^2 - y^2 \iff y^2 = x^2 - \overline{U}^2 \iff y = \sqrt{x^2 - \overline{U}^2}$,
the last step assuming the quantities can't be negative.
Note that since $\overline{U}$ is constant, then the quantity $\overline{U}^2$ is a constant, which we'll rename as $C$.
We get the family of indifference curves as $y = \sqrt{x^2 - C}$.
Differentiating w.r.t. x,
$\frac{dy}{dx} = \frac{x}{\sqrt{x^2 - C}}$
Differentiating w.r.t. x again,
$\frac{d^2 y}{dx^2} = \frac{\sqrt{x^2 - C} - x \frac{x}{\sqrt{x^2 - C}}}{x^2 - C} = \frac{\frac{x^2 - C - x^2}{\sqrt{x^2 - C}}}{x^2 - C} = \frac{-C}{(x^2 - C)^{\frac{3}{2}}}$
The quantity in the denominator is positive as long as itself and $\frac{d^2 y}{dx^2}$ well-defined and since $C = \overline{U}^2$, it is positive as long as $\frac{d^2 y}{dx^2}$ is well defined.
That well definedness I talk about occurs when $x > y$ as square roots can't be taken from negative numbers. The inside of the square root can be $0$ but the derivate wouldn't exist as the square root is in the denominator.
So we got
$\frac{d^2 y}{dx^2} < 0$ when $x > y$.
Since $x > y \iff \overline{U} > 0,$ this gives us concavity of the indifference curves for $\overline{U} \in (0,\infty)$.
The points where $y = x$ are exactly the indifference curve for $\overline{U} = 0$. Since it is a straight line, it is concave. (Lines are both convex and concave, they're kind of a wild card).
Therefore, the indifference curve for $\overline{U} = 0$ is also concave.
We got that the indifference curves for $\overline{U} \in [0,\infty)$ are concave.
Since the range of $U(x,y) = \sqrt{x^2 - y^2}$ is $[0,\infty)$, we can conclude that all the indifference curves are concave.
As you pointed out, this utility function has a negative MRS, because of the following:
$\frac{\partial U}{\partial y} = \frac{-y}{\sqrt{x^2 - y^2}}$ which is negative for all $y > 0$.
This means that $U$ is decreasing in $y$ which makes $y$ a bad rather than a good, as pointed out in the comment. This is the underlying problem.
Most of the theory is based on both $x, y$ being economic goods, i.e. the utility function is non-decreasing in both $x,y$, so you'd have to be more careful with the rules you're taught when one of the "goods" is actually an economic bad.
Note: This utility function makes no sense when $y > x$ because it would give the square root of a negative number.
On the other hand, for that Cobb-Douglas utility function, $x,y$ are both always economic goods, since
$\frac{\partial U}{\partial x} = \frac{y}{2 \sqrt{xy}}$,
$\frac{\partial U}{\partial y} = \frac{x}{2 \sqrt{xy}}$.
Since both can't be negative,
$MRS = \frac{\frac{\partial U}{\partial x}}{\frac{\partial U}{\partial y}}$ can't be negative, like you pointed out.
Edit after comment from OP:
$MU_x = \frac{\partial U}{\partial x} = \frac{x}{\sqrt{x^2 - y^2}}$,
$MU_y = \frac{\partial U}{\partial y} = \frac{-y}{\sqrt{x^2 - y^2}}$.
From here we get
$MRS_{x,y} = \frac{MU_x}{MU_y} = - \frac{x}{y}$.
The $MRS$ we usually calculate is $MRS_{x,y}$ unless stated otherwise.
Even though this is negative, when $x$ increases, the fraction $\frac{x}{y}$ gets bigger as $x$ is in the numerator and both quantities are positive.
This implies that $MRS_{x,y} = - \frac{x}{y}$ gets more negative as $x$ gets bigger. Getting more negative implies it is decreasing.