We report a new limit on a possible short range spin-dependent interaction from the precise measurement of the ratio of Larmor precession frequencies of stored ultracold neutrons and Hg199 atoms confined in the same volume. The measurement was performed in a ∼1μT vertical magnetic holding field with the apparatus searching for a permanent electric dipole moment of the neutron at the Paul Scherrer Institute. A possible coupling between freely precessing polarized neutron spins and unpolarized nucleons of the wall material can be investigated by searching for a tiny change of the precession frequencies of neutron and mercury spins. Such a frequency change can be interpreted as a consequence of a short range spin-dependent interaction that could possibly be mediated by axions or axion-like particles. The interaction strength is proportional to the CP violating product of scalar and pseudoscalar coupling constants gSgP. Our result confirms limits from complementary experiments with spin-polarized nuclei in a model-independent way. Limits from other neutron experiments are improved by up to two orders of magnitude in the interaction range of 10−6<λ<10−4m.