If you go the DIY route, XnView is freeware and will create them. You specify the sheet size in pixels and save as TIFF or JPEG.
Pixel dimensions of 2480x3500 with margins of 150 and spacing of 75 for 4 columns of 8 rows of thumbnails works for A4 sheets, with 24pt or larger text for the filenames.
The HP Photosmart printers will print index sheets of whatever JPEGs or uncompressed TIFFs are on a memory card, 16 images per page of A4.