I'm running a shoe store, so I have lots of attributes creating a lot of different indexable URLS's (shoe sizes, colours etc) - Should I submit all of these url's? Will it bring an SEO benefit or not
No it won't since the content of the URLs only varies slightly. Better tell Google that these are products with variations.
Google Video: Rich Snippets: Product Search https://www.youtube.com/watch?v=_-rRxKSm2ic