The Medrash Tanchuma (on Noach 6:5) says that 7 were born circumcised, including prior to Abraham: Adam, Seth and Noah.
Complete text as brought there:
תמים זה אחד משבעה מהולים שנולדו בעולם: אדם הראשון נברא מהול. ושת בנו נולד מהול, דכתיב: (שם ה) ויולד בדמותו כצלמו. נח נולד מהול, דכתיב: תמים היה בדורותיו. יעקב נולד מהול, דכתיב: (שם כה) ויעקב איש תם. ויוסף נולד מהול, דכתיב: (שם לז) אלה תולדות יעקב יוסף, שהיה דומה לאביו. משה נולד מהול, שנאמר: (שמות ב) ותרא אותו כי טוב הוא. ואיוב נולד מהול, דכתיב: (איוב א) איש תם וישר
... He was perfect ... This is one of the seven that was circumcised when born into the word: The first man was created circumcised, and Seth his son was born circumcised, as it says "... and he begot in his likeness after his image ..." Noah was born circumcised as it says "... He was perfect in his generations ..." Jacob was born circumcised as it says "... Jacob was an innocent man ..." Josef was born circumcised as it says "... These are the generations of Jacob: Joseph ..." that he was similar to his father. Moses was born circumcised as it says "... she saw him that he was good ..." And Job was born circumcised, as it says "... sincere and upright ...".
(Note that "sincere" in Job is the same Hebrew word as "innocent" regarding Jacob, and is the same root as the "He was perfect" regarding Noah).
So according to that lacking a foreskin was already viewed as a sign of holiness, and thus there would be no reason to think that others hadn't picked up on that and sought to imitate it.