The inverse chirp z-transform in that second paper is described as follows:

Let us now focus on the computation of the inverse chirp transform. The idea is to use the Newton basis for intermediate computations: first perform a Newton interpolation, then perform a conversion from the Newton basis to the monomial basis. Both steps have complexities M(n) + O(n), which gives the estimate of 2M(n) + O(n)

The function M(n)

denotes the cost of multiplying univariate polynomials of degree less than n. Using FFT-based multiplication algorithms, M(n) can be taken in O(n log(n) log(log(n)))

So they did not reach O(n log n).