If you haven't defeated her already, Lace is in the Drunken Cave in Begus. Go to the top right in the second area, to the lava area, not down to the ice area. The door in the building of the lava area can be used to enter a new area when you have the Katryx Blade crafted. (Make sure you equip it before the battle against Lace, and use the special skill it gives you against her.)