What an interesting find! The Biblical text in view is indeed 1 Cor 9. The key to understanding how they derived this interpretation is knowing what Clement and Eusebius meant by the words translated in the question as "greet" and "wife".
Clement explains the relationship between the apostles and women (Stromatum III, 53; Greek, English):
But the [apostles] devoted themselves to preaching without any distraction, and took their wives with them not as women with whom they had marriage relations, but as sisters, that they might be their fellow-ministers in dealing with housewives.
This is the sort of relationship Clement refers to in the quote in the question; he believes Paul to have had such a wife whom he chose not to take with him on his missionary journeys.
Eusebius quotes Clement:
Παῦλος οὐκ ὀκνεῖ ἔν τινι ἐπιστολῇ τὴν αὐτοῦ προσαγορεῦσαι σύζυγον, ἣν οὐ περιεκόμιζεν διὰ τὸ τῆς ὑπηρεσίας εὐσταλές.
Paul did not hesitate in one of his letter to προσαγορεῦσαι his consort whom he did not take around with him for the sake of convenience in his ministry.
(One word left untranslated pending discussion below.) The Greek edition of Eusebius (HUP, 1926) indicates via footnotes that 1 Cor 9 and Clement's Stromatum III are in view. Immediately after the bit quoted by Eusebius, Clement himself confirms the reference to 1 Cor 9 (Greek, English):
λεγει ουν εν τινι επιστολη ουκ εχομεν εξουσιαν αδελφην γυναικα περιαγειν, ως και οι λοιποι αποστολοι?
Accordingly he says in a letter: "Have we not a right to take about with us a wife that is a sister like the other apostles?"
This is a direct quote of 1 Cor 9:5. The phrase translated "a wife that is a sister" in the quote from Clement (αδελφην γυναικα) is nearly universally accepted to mean "a wife who is Christian" or "a believing wife", hence the English translations of 1 Corinthians. The Greek of Clement is identical to that of Paul.
The only remaining problem is that there is no "greeting” evident in 1 Cor 9. The word translated “address" (from both Clement and Eusebius) is προσαγορεύω.2 It can refer to a greeting, but also (BDAG):
to refer to someone by name or some other term, call, name, designate
It need not require a second person address ("greeting"), then. Here it probably simply refers to the "mention" or "naming" of such a woman.
Clement and Eusebius understand 1 Cor 9:5 as a reference to a wife who was a companion and fellow minister but without marital relations. In light of verse 12, they concluded that Paul (and others with him) had chosen not to take such women with them (οὐκ ἐχρησάμεθα τῇ ἐξουσίᾳ ταύτῃ = we have not made use of this right) in order not to "put an obstacle in the way of [their] ministry".
1. Anthony C. Thiselton, The First Epistle to the Corinthians: a Commentary on the Greek Text (NIGTC; Grand Rapids: Eerdmans, 2000), 680.
2. For those who care, the word is found in the NT only in Hebrews 5:10, where it is most naturally read as a designation rather than a greeting.