If you're doing it via scanning, I would suspect that an online digital printing service like blurb would be your best bet. That way, you get a nicely-bound book, whatever size you want. Print quality isn't as good as RA4 (these are the snapshots so who cares) but it's much easier and cheaper than making a bunch of cut-sheet prints and sticking/binding them into an album.
You could also look at something like Profolio (a bunch of polyethylene sleeves in a binder) but I don't think they come in square. Maybe if you had a serious guillotine you could cut one down to squareish.