This feels like a restatement of the trivially obvious observation that, if your type system is Turing complete, you're going to run into the halting problem.
It's sort of like having two languages in one. There is a first, interpreted language which manipulates Types and code and produces a program, and then a second language which is the program itself that ultimately gets typechecked and compiled. Typechecking in this case is not (necessarily) undecidable.
This paper is moreso about dependently-typed languages, where the type of one term can depend on the runtime value of another term.