I don't know about label making software, but if your A4's are a single giant sticker, then you should be able to do the following no problemo...
1. Create a graphic file in the shape of an A4 in a paint program using normalized side lengths. (e.g.- 1000 pixels for the long side and whatever pixels for the short side.) A ruler might help.
2. Draw on the labels you want. Make sure to make them all the same size for resize purposes. If you put some disks on the A4 sheets (overlapping them up to the label space on each, leaving about half an inch of extra height for the part that folds over the back of the disk) you can figure out how big to make them with respect to A4 sheet size. I think to myself something like, "this many across and that many down".
3. Print the graphic file on regular paper to test the sizes for sure. If your normalized lengths are correct, go ahead and print on your sticker sheet. You should have perfectly sized labels to cut out with your handy dandy scissors. If not, resizify the graphic or the print settings.
Sound good? I guess it's better than the disks with pencil art on them that I have. I used to smudge my fingers every time I picked up Sim Ant. :lol: