Adding foreign key on a huge table takes time

Hi,
We are using percona server 5.5. We are migrating tables from one schema into another. There are certain modifications done to the tables in target schema and is not a one to one direct movement. We are adding records into the target tables and then the constraints are created. The tables I am talking about are housing a max of half a million records. The foreign key creation is taking a lot of time. Would help if I can get a few optimization options. Thanks.

Regards
Venkatesh

Would appreciate if I can get any viewpoints around this. Thanks.