Linking Custom Content Types Together
A reference module is what you're looking for. References is the standard right now, though there are other options such as Entity Reference.

To use your reference module, add a "node reference" field to your Release content type. When configuring that field, allow it to refer only to nodes of the "Scene" content type.

For the sort order, I believe if you use the autocomplete widget for your nodereference field then it should give you sorting capabilities on the Release node-add form, without needing another field in the Scene content type or any more work in Views. Just make sure when configuring the nodereference field that you set the number of allowed node references to "unlimited".