|MadSci Network: General Biology|
From your description, I would say you have found skate egg cases. Skates are related to sharks (cartilaginous fish of the class Elasmobranchiomorphii), but flattened with wing-like fins. This group includes the Stingray as well as a number of smaller relatives, including the Winter Skate, Clearnose Skate and Barndoor skate..
The egg cases are rectangular, usually black, and leathery or parchment-like with somewhat irregular horny "spines" coming from the the four corners. The "spines" or tendrils help to entangle the pouch in seaweed and seagrass. A single skate develops inside and exits through a slit. The egg cases may wash up on shore, sometimes in large numbers. In folklore, these little pouches are called Mermaid's purses. It is likely, if there was a recent storm, that some of the egg cases washed up were not empty. This would account for the foul odor as the contents died and decayed.
Try the links in the MadSci Library for more information on General Biology.