Where It All Goes Down
The real setting from where the speaker seems to be speaking is in his own meditative mind, or in the room where he writes. This might have something to do with that surrealist crowd that Octavio Paz was known to hang out with. These were a group of artists, many of them French, that were convinced that dreams and the occult were a great way to get creative material.
So the idea of a writer digging way back into his subconscious memory is a perfect surrealist mission. Also, Melusina, who gets quite a lot of mentions in the poem, is the alter-ego of the title character in Andre Breton's surrealist novel Nadja, so we know that Paz was at least nodding in surrealism's general direction when he wrote this puppy. Sure, the setting may be the speakers mind, but the artistic context in which this poem was created is a bit easier to pin down.
Meandering in the Mind's Memory
The speaker is in a sort of hypnotic, Zen-like meditation, and it seems that sometimes he might even be dead or close to it. We get to travel through the "door of being" with him to new life, so you might even think that the setting includes the womb and the tomb. At the same time, the speaker talks a lot about walls, rooms, hotel rooms, and corridors, which can be related to the trapped feeling he has when he can't go back in time.
But he escapes that place through memory and takes the reader all over the place: Paris, Madrid, New York, Mexico City, Oaxaca, Veracruz, as well as some unnamed seashores and even to the clouds. There is a lot of emphasis on seasons, and autumn is the important one, because it is when the memory he is trying so hard to recall took place. Plus there's that direct reference to 1937 in Madrid, which tells the reader that the Spanish Civil War was important to this speaker somehow—yet another hint at the cultural and historical context out of which this poem was born.