I had a similar issue - for me it was because the foreign key index was marked as non-unique.
Presumably the query needs to do a scan to find multiple rows that match the foreign key, rather than just one?
Anyway, updating the foreign key's index to be unique changed the delete from being a scan to a seek for me.
First, it depends on how your foreign keys are declared. Assuming tables like:
CREATE TABLE parent
( pid ... not null primary key
CREATE TABLE child
, pid ... not null
references parent (pid)
on delete <action>
on update ...
action can be any of:
Produce an error indicating that the deletion or ...