I know the Gift of Men was to leave the Circles of the World, but does Tolkien ever discuss the further fate of Men? Does he talk about Heaven, Hell or Purgatory?
I remember allusions to these concepts in the fate of the Elves, and how they may be kept in the Halls of Mandos for longer or shorter periods before possibly taking up their lives again in Valinor (and maybe even returning to the East). Is there a similar discussion/explanation for the fate of Men?
No, Tolkien never wrote in any published works about a Heaven or Hell for Men, however he may have hinted at a possible afterlife for Men. As you've already stated, it was the "Gift of Men" to leave the Circles of the World and be freed from Arda. Although what this is is never discussed, Aragorn states in the Appendices to the Lord of the Rings that:
In sorrow we must go, but not in despair. Behold! we are not bound for ever to the circles of the world, and beyond them is more than memory. Farewell!
Return of the King, Appendix A: A Part of the Tale of Aragorn and Arwen
Some people speculate that Utumno was the equivalent of Hell, although that was created by Melkor.
This is not canon, because Christopher explicitly edited out references to Dagor Dagorath in the final published Silmarillion (due to a note in John's last draft that Mandos' prophecy was never heard by any but the Valar). However in earlier versions, the book concluded with Mandos telling a prophecy of the end of the world, which would describe Melkor being finally killed by a reincarnated Tūrin. From what I remember,
