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.