If someone decides to try a new mercenary will they lose all the training of their old mercenary? I would hate to hire a new one and decide I don't like it only to find I have to start all over with the old one.
Not at all. All your mercenaries retain their existing level of training - you can swap between them at will without losing anything they've already gained. You can only have one mercenary actively training at a time, though.