You need tiles with the same or bigger size as the size of tiles in your printed mosaic. If tiles in your
printed mosaic will be 1 x 1 inch and you will print it at 300DPI - you need your tiles to be no less than
300 x 300 pixels. You may use bigger tiles 400 x 400 or even 2000 x 2000 but not less than 300 x 300.
You may just use large original 4 - 6 Megapixel photos. It will takes a little longer time to save output
mosaic in this case but - IMHO - there should be not very long.
You may downsample a very large photos to some middle sizes like 640x480 or even 300 x 300, usually
it is not necessary but in case of very large libraries and mosaics it may speed up the process.
Also you may prepare a cropped photos: cut one large photo into few smaller different pictures. It's good
to get a large number of different tiles. See here for more info.