The same effect can be achieved with a single sentence:"This sentence is false". It is known as the Liar paradox and goes back to an ancient sophist Epimenides. Your two sentences simply split the Liar in two. There is no endless regress though, it ends in one step. We accept both sentences as "axioms", i.e. "true", but the second sentence implies that the first one is false, a contradiction. The problem is that in the usual proofs by contradiction there is an underlying premise that leads to it, and can be rejected, but there seems to be no such extra premise here. This means that the Liar's sentence, or your two sentences, form an inconsistent "theory": a statement and its negation can both be derived in them. By the logical law of explosion, then any sentence whatsoever can be derived in them, in other words they are uninteresting.
Detecting such self-referential paradoxes is easy enough, see e.g. Wen's Semantic Paradoxes as Equations. Your two sentences can be coded as equations x=y and y=¬x, implying x=¬x, which codes the Liar sentence x, interpreting "=" as "refers to", and ¬ as "not". The Boolean variable x can take only two values, 0 or 1, and neither fits. A collection of sentences produces a paradox if the system of equations coding it has no solution. The real question is how to interpret "no solution". Several approaches exist, all of them controversial, see Paradoxes of Self-Reference on SEP.
One way is not to interpret it at all, but to ban inconsistent theories altogether using syntax. Mathematical and logical theories go to great lengths to make sure that paradoxical "collections of sentences" are always a syntax error. This is what makes proofs by contradiction work in them. Nothing like Liar can be expressed in set theory language, for example, or in Russell's Principia, the problem is defined out of existence there.
Another approach is to declare that there is a hidden premise in the Liar after all. We implicitly assume that the sentence is either true or false, that it has a truth value. The equational interpretation shows us that this assumption is false, and we have to accept that some sentences have no truth value. We already accept this in natural language, "similar moon slowly" isn't true or false, it is gibberish, and "electron is a green dignity" is meaningless too, although it is grammatically correct. So there are different ways to be gibberish, and the Liar sentence and its cousins are "logical gibberish", still neither true nor false.
The most popular version of logic and semantics, where some syntactically correct sentences have no truth value, was developed by Kripke and is called truth value gap logic. In addition to true and false it introduces a third truth value: undefined. But such a logic creates many technical complications in assessing truth values of compound expressions and in manipulating them, so it is rarely used in mathematics or applications.