Strangely in this old fatwa they didn't quote sources even if in an Arabic version they did (see here). Basically the source is imam ibn Kathir's al-Bidaya wa an-Nihaya البداية والنهاية the translated sentence you quote is based on a statement of al-Azraqi الأزرقي (the author of a book called Akhbar Makka أخبار مكة، وما جاء فيها من الآثار) and other -not named- authors as ibn Kathir mentioned, here the Arabic quote from his book:
وقد ذكر الأزرقي وغيره أن ذا القرنين أسلم على يدي إبراهيم الخليل، وطاف معه بالكعبة المكرمة هو وإسماعيل عليه السلام. (Al-Bidaya wa an-Nihaya)
Al-Azraqi and others mentioned that Dhul-Qarnayn became Muslim at the hands of Ibraaheem (peace be upon him). And he made Tawaf with him around the Ka'aba and with Isma'ail.
and he added:
وروى عن عبيد بن عمير، وابنه عبد الله وغيرهما، أن ذا القرنين حج ماشيا، وأن إبراهيم لما سمع بقدومه تلقاه، ودعا له ورضاه، وأن الله سخر لذي القرنين السحاب يحمله حيث أراد، والله اعلم.
And he narrated from 'Obayd ibn 'Omayr and his son 'Abdullah and others that Dhul-Qarnayn performed Hajj by feet. And Ibraheem when he heard his coming came to meet him, and made supplication for him and appeased him. and Allah gave him the clouds which he sent wherever he wanted. And Allah knows best.
I found this in al-Azraqi's book here page 120ff (Chapter on the hajj of Ibraheem) and in this short version (page 22).