If one of the target creatures becomes an illegal target while Soulmates is on the stack, Soulmates resolves but doesn't enter the battlefield because its enchant ability won't be satisfied. If both targets are illegal, it doesn't resolve at all. In both of these cases, it's put directly into its owner's graveyard from the stack.
If one of the enchanted creatures leaves the battlefield without dying, Soulmates is put into its owner's graveyard, but the other creature won't be destroyed. The same is true if one of the enchanted creatures can't legally be enchanted by Soulmates (perhaps because it gained protection from enchantments or it's no longer a creature).