Cealhaidh the Corrupter can be found by using the Cold Iron on the Aelfwar around the coordinates (6181, 2605), in the Elven Palisades. Have the binding dust from your inventory on a hot bar slot, as your quest on the screen will not update the 'use' item to the dust when the Cold Iron Bar use is successful. Please note that you may be interrupted, so continue to apply the Cold Iron Bar to the mob until he either receives a debuff stating you have already applied the bar (i.e... kill this mob), or it turns into Cealhaidh.
Get Cealhaidh down to <30% health before using the Ash of Binding. The binding circle is on a timer, so if the effect disappears before Cealhaidh is killed, then you will not get credit, and you will have to find another mob to apply the Cold Iron Bar to.
Cealhaidh the Corrupter has ~3800 health and is very difficult, it is highly recommended that you bring friends.