There's no such thing as UNION ALL, as you have probably found. I think the best thing to do is do a global describe, then loop through each object (table) and issue a COUNT() type SOQL query.
UPDATE: example code. Note that this fails for tables with >50K rows
// Returns a map of the object name (all lower case) to the type object
// You can identify custom objects by the trailing '__c' string
Map<String, Schema.SObjectType> gd = Schema.getGlobalDescribe();
// declare the tables you care about; otherwise, the loop below will fail due to
// the 100 SOQL query limit
Set<String> tablesToCount = new Set<String>{'table1__c', 'table2__c', 'table3__c'};
// Store the results. If you just need a grand total of rows, you can
// just increment an Integer variable, or loop through and count the values
// in the map at the end.
Map<String, Integer> map_tableName2RecordCount = new Map<String, Integer>();
for (String typeName : gd.keySet()) {
// skip all but the tables you care about
if (!tablesToCount.contains(typeName)) continue;
System.debug('Now processing table ' + typeName);
// issue query. note that for dynamic SOQL (queries defined as Strings),
// you have to use the purpose-built Database.countQuery() method
try {
Integer count = Database.countQuery('SELECT COUNT() FROM ' + typeName);
map_tableName2RecordCount.put(typeName, count);
} catch (Exception e) {
// some objects have special query restrictions and will fail unless
// those restrictions are met (typically additional WHERE conditions)
System.debug('Oops. That query failed. Here\'s why: ' + e.getMessage());
}
}
// display the results
System.debug(map_tableName2RecordCount);