The formula is sixteen words, made of three vocatives repeated: Hare, Krishna, Rama. Hare is a vocative of Hari, a name of Vishnu, though Gaudiya Vaishnava interpretation reads it instead as a vocative of Hara, a name of Radha, so that the formula addresses the divine couple rather than one deity. Which reading is correct is a theological question internal to the tradition, and the two are not reconcilable by grammar alone.
The source is the Kali-Santarana Upanishad, and its status is worth being exact about. It is one of the minor Upanishads, of which there are more than a hundred, and it is late, it does not belong to the classical group of principal Upanishads that the great commentators treated, and it is generally placed in the late medieval period. It presents the formula as the means of crossing over the degenerate age. Citing an Upanishad for it is therefore accurate and considerably less impressive than it sounds.
The practice that made it consequential is sixteenth-century. Chaitanya Mahaprabhu, in Bengal, made congregational singing of the names, sankirtana, the central practice of the movement he founded, taken into the streets, accompanied by drum and cymbal, and open to anyone regardless of caste. That last point was the radical one and it is what the tradition itself emphasises.
The claim sometimes made that the formula is ancient Vedic is not supportable. It is medieval in its text and early modern in its practice.