We got this error while trying to export around 70K data through export to excel in Dynamics 365 CE.
Log file gave us detail of the error i.e. Excel file exceeded size lime of 4 MB.
One workaround is to export small set of data (page wise) by applying some order criteria (either in the Grid or through Advanced Find)
Or better use the wonderful Export to Excel tool in XrmToolBox
It took few mins to export the records in excel and the file size was close to 19 MB.
Hope it helps..