You should be able to use any photo or printing program to print several on the same page. Windows printing will do this as well. If you're on a Mac, you should be able to use Preview to print several JPEGs opened in the same window. Just make sure that scaling and anything other size related settings are set so that your images print at the size they should be.
As for the size, 35x45mm is 413x531 pixels at 300DPI. You may want to print them with a few mm of bleed.
If you really wanted to though, you could use Photoshop to just generate your own collage of passport photos on an A4 sized template.
Have the passports resized to 413x531px, create a new A4 image in Photoshop (or any image editing program you want to use) then drag or paste in the images and assemble them.