We report discovery of 41 new high-z quasars and luminous galaxies, which were spectroscopically identified at 5.7 < z < 6.9. This is the fourth in a series of papers from the Subaru High-z Exploration of Low-Luminosity Quasars (SHELLQs) project, based on the deep multi-band imaging data collected by the Hyper Suprime-Cam (HSC) Subaru Strategic Program survey. We selected the photometric candidates by a Bayesian probabilistic algorithm, and then carried out follow-up spectroscopy with the Gran Telescopio Canarias and the Subaru Telescope. Combined with the sample presented in the previous papers, we have now spectroscopically identified 137 extremely-red HSC sources over about 650 deg2, which include 64 high-z quasars, 24 high-z luminous galaxies, 6 [O III] emitters at z ~ 0.8, and 43 Galactic cool dwarfs (low-mass stars and brown dwarfs). The new quasars span the luminosity range from M1450 ~ -26 to -22 mag, and continue to populate a few magnitude lower luminosities than have been probed by previous wide-field surveys. In a companion paper, we derive the quasar luminosity function at z ~ 6 over an unprecedentedly wide range of M1450 ~ -28 to -21 mag, exploiting the SHELLQs and other survey outcomes.