If a pregnant divorced gentile woman marries a different man and then conceives another child of opposite gender through superfetation, are the twins considered only half-siblings and permitted to marry?
Yichus for nonjews according to Jewish law follows the mother. See Rambam hilchos milachim umilchamos chapter 9 halacha 5. Therefore these children are complete siblings as far as we are concerned.
I would like to add for the sake of clarity however that even relationships that are allowed such as a father marrying a daughter are off limits due to the fact that the non-Jews already decided to distance themselves from forbidden arayos. This is what the gemara meant by saying Lot's intentions were for an aveira, see tosafos in maseches Nazir 23a.