The problem you have is that you are going for approximately a 4 X enlargement to start with (6X4 to A4). If you want the best result possible you should really go for photographic enlargement from the negative. Failing that, from the photo print.
If you want to use the photo printer, then I think you would have done better to do any photo manipulation in TIFF. Then convert (full size) to a low compression JPEG. You really need to end up at the printer with as many pixels as your memory will allow as the photo-print process is very demanding. If you reduce the image information too far you will end up with a grainy and pixellated image - not very nice.