1) You have the answers right in front of you..lol! A0-A18 are good for 512 KB, so use A19 to enable the second 512KB. That is 1 MB so far. Use A0-A19 with A20 to enable the next 1 MB IC. Use A0-A20 with A21 used to enable the last 1 MB.
2) If you wire A18, A19 and A20 to a 74AC138 address select(74LVC138 if 3.3 volt memory), it will give you 8 blocks of 512 KB that are active low Y0-Y7. You MUST control the chip select pins (CS) so that the outputs go low after the address lines are stable. Only one 'Y' pin at a time can go low.
3) Make sure you wire up all needed address lines, stoping at A20. Use Y0 and Y1 for the first two 512 KB chips. Use Y4 && Y5 to enable the first 1 MB chip, and Y6 && Y7 to enable your last 1 MB. The && I typed means use a fast 74AC08 AND gate or 74LVC08 if 3.3 volt logic to sum together 2 'Y' address lines, with a single active low output for your 1 MB IC's.
4) Don't forget to wire up your active low read (RD) and write (WR) lines. They should be the last lines to be active, though some designs may use chip select (CS) as a final strobe after all other lines are settled to a study state.
5) Why you thought you needed 30 to 40 address lines I do not know (That would be for GB of memory). If the lower addresses are already in use shift the Y0 and Y1 lines to Y2 and Y3, which gives you 1MB of spare room at the bottom of your memory map.
NOTE: If you are trying to add this to an existing memory map with lots of I/O already in use then I would re-think this. Once you understand memory mapping you will know what you can and cannot do.