We numerically investigate decoherence of a two-spin system (central system) by a bath of many spins 1/2. By carefully adjusting parameters, the dynamical regime of the bath has been varied from quantum chaos to regular, while all other dynamical characteristics have been kept practically intact. We explicitly demonstrate that for a many-body quantum bath, the onset of quantum chaos leads to significantly faster and stronger decoherence compared to an equivalent non-chaotic bath. Moreover, the non-diagonal elements of the system's density matrix, the linear entropy, and the fidelity of the central system decay differently for chaotic and non-chaotic baths. Therefore, knowledge of the basic parameters of the bath (strength of the system-bath interaction, and the bath's spectral density of states) is not always sufficient, and much finer details of the bath's dynamics can strongly affect the decoherence process.