It is a non-finite verb; it is not an inflected verb in the sentence. It is not part of a prepositional phrase. "finding them" is a participial clause.
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.
Guyper"They didn't have much luck to find them"?No. The infinitive can follow (complement) certain nouns and adjectives, but not this one.
GuyperWas a preposition omitted between luck and finding?A preposition is not necessary. If you wanted a preposition there, it would be "in," but it would not change the -ing form of finding.