count(*) doesn't do full table scan as it's not tied to specific data. It has special handling logic. The only case where it might have to do a full table scan is if you try to count() on a specific (nullable?) column without an index.
It is optimized in MyISAM via table-level metadata, which is only possible because MyISAM doesn't use MVCC or support transactions.
In InnoDB, you can get an estimated row count from SHOW TABLE STATUS, but the estimate is based on table stats and can be wildly inaccurate.