Delete from table using FK columns, JOIN and LIMIT
This workaround is OK for my case but isn't great, since it needs to scan the entire index of the User table, so wouldn't be very portable. The user:product ratio can be up to 1:1000, and it's feasible to scan the User table first using a covering index before doing the JOIN.

DELETE 
FROM Product f 
JOIN ( 
    SELECT t.* FROM (
        SELECT DISTINCT user_type, user_id
        FROM UserTable
        WHERE MOD(shard_key,20) != 7
        ) p
        JOIN Product t ON (
            t.user_type = p.user_type 
            AND 
            t.user_id = p.user_id
        ) LIMIT 10 
    ) x 
ON 
x.user_type = f.user_type 
AND 
x.user = f.user_id;


My takeaway is: If you can reasonably scan the entire primary key table quickly using indexes, and join with the foreign key table afterwards (ideally also using indexes), that is a solution that ensures you will be able to find ALL foreign key references if you want to batch DELETE in situations where many foreign keys reference each primary key.In this case, the User table was ~1GB and the Product table ~350GB