Thanks James,
I was trying to avoid making a query table but it seems that's the the quickest approach that doesn't require iterating. However using the MakeQueryTable tool did require spinning up the geoprocessor which took some time so in the end I actually found it was still faster to just iterate and count the rows.
with arcpy.da.SearchCursor(FeatureLayer, "SHAPE@", SuperDuperAwesomeQuery) as rows:
rowCount = 0
for row in rows:
rowCount = rowCount + 1
print rowCount
del rows