I use the Python Excel module openpyxl. Please download this if it's not currently installed. The below code should work if the module is installed correctly. Please create an empty .xlsx file and set the path to the variable in line 26.
import arcpy
import os
from openpyxl import Workbook
db = r'path_to_geodatabase_.gdb'
arcpy.env.workspace = db
wb = Workbook()
ws = wb.active
ws['A1'] = 'FeatureClass'
ws['B1'] = 'Count'
count = 2
for ds in arcpy.ListDatasets():
for fc in sorted(arcpy.ListFeatureClasses('','',ds)):
fc_path = os.path.join(db, fc)
fc_count = str(arcpy.GetCount_management(fc_path))
print "{0} : {1} rows".format(fc, fc_count)
ws['A{0}'.format(count)] = fc
ws['B{0}'.format(count)] = fc_count
count += 1
output = 'path_to_output_Excel_.xlsx'
wb.save(output)