Infinite loops in TeX

When TeX sees \par, it makes a paragraph, building lines of text; when a sufficient number of lines is reached, it ejects a page and removes it from its memory. So it never runs out of memory with the first loop.

In the second case, it continues storing tokens until a paragraph ends. Which doesn't happen, obviously, before memory is exhausted.

It's important to note that when a macro is expanded, it is replaced by its replacement text and the original token disappears. However, the tokens Hello! are in both cases sent to the internal processor for building boxes.

As egreg says the difference between your examples is the different size of the paragraph being built.

Just considering expansion there are other variants with different failure messages. TeX macro expansion uses tail recursion elimination so if a recursive call is the final item in the replacement the input stack is popped before the recursive call, and so there is no stack usage.

If you have

\def\x{Hello!\par\x\relax}
\x

which is a non tail-recursive variant of your first example, tex dies much earlier:

! TeX capacity exceeded, sorry [input stack size=5000].
\x ->H
      ello!\par \x \relax 
\x ->Hello!\par \x 
                   \relax 
\x ->Hello!\par \x 
                   \relax 
\x ->Hello!\par \x 
                   \relax 
\x ->Hello!\par \x 
                   \relax 
\x ->Hello!\par \x 
                   \relax 
...
l.2 \x

and you get essentially the same error with the second version as the input stack is more restrictive than main memory

\def\x{Hello!\x\relax}
\x