Super-parallel performance of a mixed explicit discontinuous Galerkin method is reported for the second-order Boltzmann-based nonlinear coupled constitutive models of rarefied and microscale gases. One of the challenging issues in the discontinuous Galerkin (DG) method is the higher computational cost compared with the traditional finite volume method (FVM) for a given set of grids. In the present study, we focus on the computational cost of a mixed modal explicit DG method for solving the conservation laws in conjunction with the first- and second-order Boltzmann-based constitutive models, in particular, in the context of parallelization of the implicit algebraic constitutive equations of rarefied and microscale gases in continuum and transition regimes. The computational cost of the Navier-Stokes-Fourier (NSF) and nonlinear coupled constitutive relation (NCCR) solvers is investigated in the serial and parallel frameworks. It was shown that the computational cost of the NCCR solver behaves nonlinearly with respect to the number of elements, due to the dependence of the number of iterations of the NCCR solver on the flow structure and the degree of thermal non-equilibrium. Such nonlinear dependence was clearly demonstrated from numerical solutions of three representative flows; flat plate, cylinder, and wedge. Ultimately, this nonlinear behavior of computational cost associated with nonlinear performance of the DG-NCCR solver resulted in an unexpected super-parallel performance in parallel processing.