Compositing 2 images

There are so many ways you could do that.  Conrad mentioned Canvas size (Ctrl Alt C),

You could create a new document and add both images to it.

You could use the Crop tool, and drag the handles outside the initial boundaries.

You mention the finished image being more than the combined size of the source images.  Do you intend stretching the images to fill that size?  That's going to lose some image quality.  If you havr the beta version installed, then you could fill the gaps with Generative Fill.

You mentioned Replace Sky.  One thing it does is produce outstandingly good selections of the sky/foreground interface, so I often use it just to to get that selection to make a mask for a composite. 

I am not sure what you mean when you said you are losing 801% of the sky replacement.  Do the donor images have wildly different pixel sizes?  If so, you are going to have to downsize (Free Transform) the larger one to fit if you want to avoid losing quality of the smaller image.

If you don't mind showing us the two images, it will make it a lot easier to help you.

What is not working about increasing the size of the image or canvas? Is it displaying an error, like a size limit? Because normally, increasing the canvas size should give you the additional room you need.