What you are doing now is translated to SQL as:
SELECT * FROM MyTable
WHERE
Foo = 1 OR
Foo = 2 OR
Foo = 3 OR
Foo = ... OR
Foo = 4500
Instead you could use an IN clause like:
SELECT * FROM MyTable
WHERE Foo IN (1,2,3,...,4500)
For that you can use FieldCompareRangePredicate. Now, SQLServer has a parameter limitation. If I'm not wrong the limit is 2100 params. That means you can't do this in one shot. You have to fetch the records in small pieces. For instance:
// this retrieves the first 2000 items from customers_list
List<int> firstBucket = GetBucketOfIds(1, 2000);
IRelationPredicateBucket filter1 = new RelationPredicateBucket();
filter1.Add(MyTableFields.Foo == firstBucket);
EntityCollection<MyTableEntity) firstCollection = new EntityCollection<MyTableEntity>();
adapter.FetchEntityCollection(firstCollection, filter1);
// do the same 2 or 3 times to fetch the other collections
// now you can merge the 2 or 3 sub collections
Other way is that you can insert those Ids into a temp table in your database. Now you can do a FieldCompareSetPredicate to do it in one shot.