If you're getting it printed the printer will probably have a press that does slightly over A2 or A3 size (for example, a Heidelberg GTO52 will accept paper up to 52cm wide by 36cm high, about 20% longer and wider than an A3 sheet). Paper merchants can cut paper to size, but often the manufacturers supply paper in stand 'SRA' sizes that are slightly larger than the corresponding ISO 'A' size.
For example, SRA2 is 640mm x 450mm whereas A2 is 594mm x 420mm. SRA3 is 450mm x 320mm; ISO define various 'SRA' sizes for each corresponding 'A' size. Often it is cheaper to get the paper in these sizes because it can be bought pre-cut with minimal wastage.
If you want a square brochure with gate folded sides then the ratio of width to height you want will be 2:1 (twice as wide as it is high).
A little research on the cost of the paper may allow you to optimise the size of the brochure for stock that the printer can get a little more cheaply. If you can base your design on something that can be printed on standard stock then the paper may be a little cheaper. Find out how wide the press you intend to use will print (typically it will need a couple of centimetres each end for cut marks and such like).
For SRA3, you can expect to get at least 420mm (the width of A3) plus the excess. In this case, you could have a brochure that is 420x210. With SRA2 you could get something that is about 600x300. The printer's finishing people will just cut off the excess paper with a guillotine.
Alternatively, you can size the brochure to the press. In the case of the GTO52, the largest practical image you can print is a little under 50cm wide, with bleeds. This might allow you to make a brochure that is something like 48cm x 24cm open or 24cm x 24cm closed.
For a 2:1 width to height ratio you are unlikely to get an efficient custom cut from SRA0 unless you want to make your brochure quite small. You might be able to get 5x2 cut of 256 x 450 off a SRA0 sheet, from which you could print a final product around 42cm x 21cm. This would let you do your final square cut without too much wastage of the original paper stock.
Note that the paper cost will be significant for a large run, but for small print runs (say less than 10,000) the artwork and plates will dominate the costs, so busting a gut to economise on paper may be more trouble than it's worth.