since all lenses are round, full frame cameras' sensors can be 36 × 36 millimeters. Correct? Is it possible, and if so, why it has not been done yet? Would that qualify it as medium format?
That's not correct. Look at this picture:
The green rectangle is a 36x24 sensor. The green circle, which has a diameter of 43.3mm, is the minimal light spot needed for that size. The blue square is 36x36 sensor. The blue circle, which has a diameter of 50.9mm, is the minimal light spot needed for that size. As you can see a lens suitable for 36x24 does not necessarily cover the whole 36x36 frame.
As for the second part of your question - it is possible to qualify such sensors (in my opinion) as medium format because the most of available "full-frame" lenses will not cover these bigger sensors and so you'll need other lenses.
Is it possible and why it has not been done yet ?
Not necessarily. A 24x36mm sensor will easily fit in an image circle that's too small for a 36x36mm sensor. Specifically, a 24x36mm sensor requires a minimum diameter of about 44mm to cover the sensor. A 36x36mm sensor would require an image circle of about 51mm diameter. A square sensor is certainly possible, but square frames were possible with film as well.
The diameter of the image circle has to be at least as large as the sensor diagonal. You can see from the diagram that the green 24x36mm rectangle fits within the yellow image circle, but a 36mm square does not -- the corners fall outside the image circle and will be dark.
There's a variety of aesthetic and practical reasons that non-square images are preferred. Indeed, people often prefer images that are even wider than the 3:2 aspect ratio that we have in the typical full frame sensor.
If you prefer square images for any reason, you can set many cameras to record a square image, or you can crop after the fact.
The sensors could be made to a square format (though the current diameter would not accommodate 36x36mm, it would need to be about 30mm) if there was a demand for it. But by that logic the question we may actually need to be answering is why aren't sensors circular given that lenses present a circular image?
There were some attempts at circular sensors in the phone space when Nokia were working on the PureView cameras like the 808 before PureView just became a marketing thing for their best cameras. The camera then used the surface area it needed to make the chosen aspect.
One of the things is that inside a DLSR you also need space for a mirror to move into and also for a shutter mechanism. While the shape of cameras could change to accommodate it, it's a lot of R&D for a small payoff.
It's also telling that even the medium format cameras use a non-square sensor with the Leica S, Pentax 645D, Leaf AFi, Hasselblad H5D and PhaseOne medium-format systems all adopt a rectangular aspect-ratio similar to the 6x4.5 systems than 6x6.
Any increase in sensor area also means a non-linear drop in wafer yield (the number of useful sensors you can get out of a silicon wafer) as demonstrated graphically in this answer - again it's extra cost.
Little payoff is where the idea really falls down - Canon, Nikon, Sony etc all put huge amounts of money into R&D, if any of them thought there was a viable market then they'd go for it. I'm not seeing one and the lack of such DSLR cameras on the market would back that up.
Square is not necessarily larger. 24 megapixels will hold:
3:2 6000x4000 pixels
4:3 5657x4243 pixels
1:1 4899x4899 pixels
And "pictures" have mostly always been rectangular, from most film, and paintings too (like Rembrandt). We did have square medium film, but the print paper was rectangular . It seems a matter of strong preference.