We report the discovery of 41 new high-z quasars and luminous galaxies that 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 using 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 deg(2),which includes 64 high-z quasars, 24 high-z luminous galaxies, 6 [O III] emitters at z similar to 0.8, and 43 Galactic cool dwarfs (low-mass stars and brown dwarfs). The new quasars span in luminosity range from M-1450 similar to -26 to -22 mag, and continue to populate luminosities a few magnitudes lower than have been probed by previous wide-field surveys. In a companion paper, we derive the quasar luminosity function at z similar to 6 over an unprecedentedly wide range of M-1450 similar to -28 to -21 mag, exploiting the SHELLQs and other survey outcomes.